#include "pentominoes.h"
#include <boost/utility.hpp>

#include <boost/tuple/tuple.hpp>
#include <boost/tuple/tuple_io.hpp>

#include <sstream>
#include <typeinfo>
#include <iostream>
#include <algorithm>

/*
 * OutOfBoundException : what (public const member function...)
 * Args                : None
 * Returns             : String(in form of const char*)
 * Throws              : Nothing
 * Defn                :
 *                       This exception is thrown when the overlap of one matrix-model
 *                       on another crosses 
 *                       the boundary of the second.
 */
const char* 
OutOfBoundException::what() const throw()
{
    std::stringstream oss;
    static std::string mystr;
    mystr = "" ;
    oss << "OutOfBound Exception: The amount in X and Y dir by which out of bound occured = " ;
    oss << boost::tuples::set_open('[') << boost::tuples::set_close(']') <<
        boost::tuples::set_delimiter(',') << m_data ;
    oss << std::endl ;

    mystr=oss.str();
    return mystr.c_str() ;
}

/*
 * BindException       : what (public const member function...)
 * Args                : None
 * Returns             : String(in form of const char*)
 * Throws              : Nothing
 * Defn                :
 *                       This exception is thrown when the one matrix can not be bound
 *                       on another
 */
const char* 
BindException::what() const throw()
{
    std::stringstream oss;
    static std::string mystr;
    mystr = "" ;
    oss << "Bind Exception : The Bind operation failed at  = " ;
    oss << boost::tuples::set_open('[') << boost::tuples::set_close(']') <<
        boost::tuples::set_delimiter(',') << m_data ;
    oss << std::endl ;

    mystr=oss.str();
    return mystr.c_str() ;
}

/*
 * UnbindException     : what (public const member function...)
 * Args                : None
 * Returns             : String(in form of const char*)
 * Throws              : Nothing
 * Defn                :
 *                       This exception is thrown when the one matrix can not be unbound
 *                       from another
 */
const char* 
UnbindException::what() const throw()
{
    std::stringstream oss;
    static std::string mystr;
    mystr = "" ;
    oss << "Unbind Exception : The Unbind operation failed at  = " ;
    oss << boost::tuples::set_open('[') << boost::tuples::set_close(']') <<
        boost::tuples::set_delimiter(',') << m_data ;
    oss << std::endl ;

    mystr=oss.str();
    return mystr.c_str() ;
}

/*
 * InvalidOrientationException     : what (public const member function...)
 * Args                            : None
 * Returns                         : String(in form of const char*)
 * Throws                          : Nothing
 * Defn                            :
 *                                   This exception is thrown when the orientation being set
 *                                   is invalid
 */
const char* 
InvalidOrientationException::what() const throw()
{
    std::stringstream oss;
    static std::string mystr;
    mystr = "" ;
    oss << "Invalid Orientation Set : " ;
    oss << m_orient ;
    oss << std::endl ;

    mystr=oss.str();
    return mystr.c_str() ;
}

/*
 * InvalidOrientationException     : what (public const member function...)
 * Args                            : None
 * Returns                         : String(in form of const char*)
 * Throws                          : Nothing
 * Defn                            :
 *                                   This exception is thrown when the letter of the
 *                                   pentominoes piece being set is invalid
 */
const char* 
InvalidLetterException::what() const throw()
{
    std::stringstream oss;
    static std::string mystr;
    mystr = "" ;
    oss << "Invalid Letter : " ;
    oss << m_letter ;
    oss << std::endl ;

    mystr=oss.str();
    return mystr.c_str() ;
}

// Implementation of matrix Model...

/*
 * MatrixModel : Default Constructor (public)
 * Args        : None
 * Returns     : Constructed MatrixModel object...
 * Throws      : Nothing
 * Defn        :
 *       Builds a dummy MatrixModel with 0 size, i..e both row and columns are
 *       of size 0. The orientation is also set to R0.
 *
 *Note         :       
 *       MatrixModel can be reset to desired size using initialize member function.
 *       
 */ 
MatrixModel::MatrixModel() : m_data(), m_dimension(), m_orient(R0)
{
    m_dimension.get<0>() = 0 ;
    m_dimension.get<1>() = 0 ;    
}

/*
 * MatrixModel : Constructor   (public)
 * Args        : Dimension of the model as UIntPair
 * Returns     : Constructed MatrixModel object...
 * Throws      : Nothing
 * Defn        :
 *               Builds a MatrixModel of the size passed as argument. The first item
 *          of the pair is treated as count of rows and second as column. Each row of
 *          the matrix is initialized with a dynamic_set with size as no. of columns.
 *          The dynamic_bitset is initialized with 0(false) for all the rows of the
 *          matrix. The orientation of the MatrixModel is initialized as R0.
 * Notes       :
 *               All the initialization of the MatrixModel is done through the public
 *          member function 'initialize'
 *            
 */ 
MatrixModel::MatrixModel(UIntPair& data) : m_data(), m_dimension(data), m_orient(R0)
{
    unsigned int row = data.get<0>() ;
    unsigned int col = boost::get<1>(data) ;
    this->initialize(row, col) ;
}

/*
 * MatrixModel : Constructor   (public)
 * Args        : row, col
 * Returns     : Constructed MatrixModel object...
 * Throws      : Nothing
 * Defn        :
 *               Builds a MatrixModel of the size passed as argument. Each row of
 *          the matrix is initialized with a dynamic_bitset with size as no. of columns.
 *          The dynamic_bitset is initialized with 0(false) for all the rows of the
 *          matrix. The orientation of the MatrixModel is initialized as R0.
 * Notes       :
 *               All the initialization of the MatrixModel is done through the public
 *          member function 'initialize'
 *            
 */
MatrixModel::MatrixModel(unsigned int row, unsigned int col) : m_data(), m_dimension(),
                                                               m_orient(R0)
{
    this->initialize(row, col) ;
}

/*
 * MatrixModel  : Destructor
 * Args         : None
 * Returns      : None
 * Throws       : Nothing
 * Defn         :
 *               Clears the bit vector 2D matrix
 *               Resets the dimension of the matrix to (0,0)
 */ 
MatrixModel::~MatrixModel()
{
    for(unsigned int i = 0; i < m_dimension.get<0>(); ++i)
        m_data[i].clear() ;
    m_data.clear() ;
    m_dimension.get<0>() = 0 ;
    m_dimension.get<1>() = 0 ;
}

MatrixModel&
MatrixModel::operator=(const MatrixModel& model)
{
    if (this == &model)
        return *this ;
    m_data = model.m_data ;
    m_dimension = model.m_dimension ;
    m_orient = model.m_orient ;

    return *this ;
}


/*
 * MatrixModel : modelCompare (public const member function)
 * Args        : const MatrixModel to compare to
 * Returns     : bool (true  - both models are equal after comparing by value.
 *                     false - models are not equal after comparing by value.
 * Throws      : Nothing
 * Defn        :
 *               1. Compare the dimensions of the matrix if not equal return false.
 *               2. Iterate upon both the matrix and comapre the value at the indices
 *                  if any comparison fails, return false
 * Notes       :
 *               The raw matrix models are compared and no transformations are applied
 *               to get the matrix coord. In other words both the matrices are considered
 *               to be in R0 state and compared(MatrixModel could be in non R0 orientation).
 *
 *               modelCompare is possible as no matter what orientation the current matrix
 *               is, there is only one raw model to store the values. Transformations are
 *               applied to get to the correct indices from this raw models and values are
 *               used.
 * 
 */ 
bool
MatrixModel::modelCompare(const MatrixModel& matrix) const
{
    if (m_dimension.get<0>() != matrix.m_dimension.get<0>() ||
        m_dimension.get<1>() != matrix.m_dimension.get<1>())
        return false ;
    for(unsigned int i = 0 ; i < m_dimension.get<0>(); ++i) {
        if (m_data[i] != matrix.m_data[i])
	    return false ;
    }
    return true ;
}

/*
 * MatrixModel : deepCompare (public, const member function.)
 * Args        : const MatrixModel to compare to
 * Returns     : bool (true  - models are equal after comparing by value,
 *                             post transformation.
 *                     false - models are not equal after comparing by value,
 *                             post transformation.)
 * Throws      : InvalidOrientationException (through
 *                    doCurTransformedValCompare->getInverseTransformMat)
 * Defn        :
 *               1. Compare the dimensions of the matrix if not equal return false.
 *               2. Iterate upon both the matrix and comapre the value at the indices
 *                  if any comparison fails, return false. Iteration will be done on
 *                  transformed row count and col count. Also the values at indices will be
 *                  accessed post transformation.
 * Notes       :
 *               The transformed matrix models are compared. The iteration happens on (row,col)
 *               which is transformed depending upon the orientation. The goal is to try to make
 *               the matrices equal. All possile transformations are applied on the current model
 *               post which value comparision is done. In any case equal or not the
 *               current orientation is stored prior to the comparision operation and
 *               reset to its normal value after comparison is done.
 *
 *               Sigh.. const_cast is used.
 */ 
bool
MatrixModel::deepCompare(const MatrixModel& matrix) const
{
    if (m_dimension.get<0>() != matrix.m_dimension.get<0>() ||
        m_dimension.get<1>() != matrix.m_dimension.get<1>())
        return false ;
    
    Orientation curOrient = m_orient ;
    Orientation nxtOrient = curOrient ;
    MatrixModel* p_curModel = const_cast<MatrixModel*>(this) ;
    do {
        p_curModel->m_orient = nxtOrient ;
        if(doCurTransformedValCompare(matrix)) {
  	    p_curModel->m_orient = curOrient ;
            return true ;
	}
        nxtOrient = (Orientation)((nxtOrient + 1) % MAXORIENT) ;
    } while (nxtOrient != curOrient) ;
    p_curModel->m_orient = curOrient ;
    return false ;
}

/*
 * MatrixModel : numRows (public const member function...)
 * Args        : None
 * Returns     : No. of rows in the matrix(unsigned int)
 * Throws      : InvalidOrientationException
 * Defn        :
 *               If the orientation is R0 or FR0 or oienatation which could be got after
 *               rotating it by 180 degress return the first item of the dimension else
 *               returns the second item of the dimension.
 * Notes       : The raw matrix model is stored in R0 format, hence the dimension of this
 *               raw model will be topologocal similar to R180, FR0 and FR180 and would
 *               be reverse for other orientations.
 */
unsigned int
MatrixModel::numRows() const
{
    switch(m_orient)
    {
        case R0 :
        case R180 :
        case FR0 :
        case FR180 :
  	    return m_dimension.get<0>() ;
        case R90 :
        case R270 :
        case FR90 :
        case FR270 :
  	    return m_dimension.get<1>() ;
        default : 
	    break ;
    }
    throw InvalidOrientationException(m_orient) ;
}

/*
 * MatrixModel : numCols (public const member function...)
 * Args        : None
 * Returns     : No. of cols in the matrix(unsigned int)
 * Throws      : InvalidOrientationException
 * Defn        :
 *               If the orientation is R0 or FR0 or oienatation which could be got after
 *               rotating it by 180 degress return the second item of the dimension else
 *               returns the first item of the dimension.
 * Notes       : The raw matrix model is stored in R0 format, hence the dimension of this
 *               raw model will be topologocal similar to R180, FR0 and FR180 and would
 *               be reverse for other orientations.
 */
unsigned int
MatrixModel::numCols() const
{
    switch(m_orient)
    {
        case R0 :
        case R180 :
        case FR0 :
        case FR180 :
   	    return boost::get<1>(m_dimension) ;
        case R90 :
        case R270 :
        case FR90 :
        case FR270 :
            return boost::get<0>(m_dimension) ;
        default : 
	    break ;
    }
    throw InvalidOrientationException(m_orient) ;
}

/*
 * MatrixModel : getValAt (public const member function...)
 * Args        : row, col, posTransform(bool)
 * Returns     : boolean value at (row,col) in the MatrixModel
 * Throws      : InvalidOrientationException (through :
 *                   applyInverseTransformToWorld->getInverseTransformMat)
 * Defn        : If the postTransform is passed as false, merely return the values at
 *               (row,col) from the raw matrix Model. Otherwise transform the given
 *               coord(row, col) using the inverse-transform-matrix for the
 *               orientation of the model and get the value at the transformed coord in
 *               the raw matrix model.
 *               
 *               The new coord is got from another member function
 *               applyInverseTransformToWorld, the new coord is basically the coord
 *               one need to look at in the raw matrix model.
 *               
 *               Steps : (if postTransform is true)
 *                  1. Convert the current coord to new coord aftter applying the transform
 *                  2. Get the value from the raw-matrix model at coord got at step 1.
 *                  
 * Sighs       : What if (row,col) itself is not valid either the one given when
 *               postTransform is false or the coord got after applying transformation
 *               when postTransform is true. (HANDLE THIS)
 */
bool
MatrixModel::getValAt(unsigned int row, unsigned int col, bool postTransform) const
{
    if (!postTransform)
        return m_data[row][col] ;
    UIntPair matrixCoord = boost::make_tuple(row, col) ;
    matrixCoord = applyInverseTransformToWorld(matrixCoord) ;
    return m_data[matrixCoord.get<0>()][matrixCoord.get<1>()] ;
}

/*
 * MatrixModel : setValAt (public const member function...)
 * Args        : row, col, val(value to set), posTransform(bool)
 * Returns     : boolean value at (row,col) in the MatrixModel
 * Throws      : InvalidOrientationException (through :
 *                   applyInverseTransformToWorld->getInverseTransformMat)
 * Defn        : If the postTransform is passed as false, merely set the value val at
 *               (row,col) from the raw matrix Model. Otherwise transform the given
 *               coord(row, col) using the inverse-transform-matrix for the orientation
 *               of the model and set the value val at the transformed coord in the
 *               raw matrix model.
 *               
 *               The new coord is got from another member function
 *               applyInverseTransformToWorld, the new coord is basically the coord
 *               one need to work in the raw matrix model.
 *               
 *               Steps : (if postTransform is true)
 *                  1. Convert the current coord to new coord aftter applying the transform
 *                  2. Set the value val in the raw-matrix model at coord got at step 1.
 *                  
 * Sighs       : What if (row,col) itself is not valid either the one given when
 *               postTransform is false or the coord got after applying transformation
 *               when postTransform is true. (HANDLE THIS)
 */
void
MatrixModel::setValAt(unsigned int row, unsigned int col, bool val, bool postTransform)
{
    if (!postTransform) {
        m_data[row][col] = val ;
	return ;
    }
    UIntPair matrixCoord = boost::make_tuple(row, col) ;
    matrixCoord = applyInverseTransformToWorld(matrixCoord) ;
    m_data[matrixCoord.get<0>()][matrixCoord.get<1>()] = val ;
}

/*
 * MatrixModel : getLowestPosWithVal (public const member function)
 * Args        : val       : value to look for in the matrix-model
 *               worldPos  : Transformed world coord to be returned as
 *                           per the orientation of the model.
 *               dir       : The search direction (row-major or column-major)
 * Returns     : true  - if the desired value 'val' is found.
 *               false - if nosuch value as 'val' is found.
 * Throws      : InvalidOrientationException (through getInverseTransformMat)
 * Defn        : The matrix is iterated(iteration is performed on the transformed
 *               (row, col) of the raw matrix model) to find the val. As the iteration
 *               is done on transformed (row, col) the transformation is applied every
 *               time for the cuurent coord in the iteration to get equivalent
 *               raw-matrix coords. Once the desired value is found, the worldPos
 *               ref-variable is populated and true returned, else a false is returned
 *               from the function.
 * Notes       : The function always populates the WORLD POS, the defn of world and matrix pos is
 *               defined below.
 *               WORLD POS  = The coord got after transforming the coord in raw-matrix model
 *                            The world pos can also be defined as the coord got after
 *                            iterating upon row,col where this row and col is got using
 *                            numRows and numCols
 *               MATRIX POS = Matrix pos is the coord in the raw matrix model.
 *
 *               MATRIX POS -> (Apply Transformation Matrix)        -> WORLD  POS
 *               WORLD  POS -> (Apply Inverse Transformation Matrix)-> MATRIX POS
 *               
 */ 
bool
MatrixModel::getLowestPosWithVal(bool val, UIntPair& worldPos, DIR dir) const
{
    unsigned int row = numRows() ;
    unsigned int col = numCols() ;
    int transformMat[3][3] ;
    getInverseTransformMat(transformMat) ;

    if (dir == X_DIR) {
        for(int i = 0; i < (int)row; ++i) {
            for(int j = 0; j < (int)col; ++j) {
                // (i,j) is worldCoord.
                IntPair curCoord = boost::make_tuple(i, j) ;  
                IntPair matCoord = getMatrixCoord(curCoord, transformMat) ;
                int curRow = matCoord.get<0>() ;
                int curCol = matCoord.get<1>() ;
                if (m_data[curRow][curCol] == val) {
                    worldPos = boost::make_tuple((unsigned int)i, (unsigned int)j) ;
                    return true ;
                }
            }
        }
    } else if (dir == Y_DIR) {
        for(int j = 0; j < (int)col; ++j) {
            for(int i = 0; i < (int)row; ++i) {
                // (i,j) is worldCoord.
                IntPair curCoord = boost::make_tuple(j, i) ;  
                IntPair matCoord = getMatrixCoord(curCoord, transformMat) ;
                int curRow = matCoord.get<0>() ;
                int curCol = matCoord.get<1>() ;
                if (m_data[curRow][curCol] == val) {
                    worldPos = boost::make_tuple((unsigned int)i, (unsigned int)j) ;
                    return true ;
                }
            }
        }        
    }
    return false ;
}

/*
 * MatrixModel : bindMatrixAt (public member function, non-const)
 * Args        : matrix   : The matrix whose elements need to be applied on the current
 *                          matrix model.
 *               worldPos : worldPos Pos of the current matrix (in WORLD POS and not in
 *                          MATRIX POS).
 * Returns     : Nothing
 * Throws      : BindException, InvalidOrientationException (through getInverseTransformMat)
 * Defn        :
 *               Maps the input matrx at worldPos, such that the (0,0) of the input matrix is
 *               at worldPos of the current matrix.
 * Algo        :
 *               1. Calculate the available space on the right and bottom of the current matrix
 *                  starting from worldPos. (residueRow, residueCol)
 *               2. If (residueRow < (rowCnt of inputMatrix)) or
 *                     (residueCol < (colCnt of inputMatrix))
 *                     throw BindException
 *               3. Iterate inputMatrix form (0,0) to (rowCnt, colCnt of inputMatrix)
 *                  Iterate currentMatrix form (worldPos) to (rowCnt, colCnt of currentMatrix)
 *               4. Get the equivalent MatrixPos coords of the coords got at step 3
 *               5. copy if there is a true val at the coord calculated at step 3 in
 *                  input matrix to
 *                  current matrix. But if the current matrix already contains a true at
 *                  the location
 *                  calculate at step 3. throw abind Exception
 */ 
void
MatrixModel::bindMatrixAt(const MatrixModel& matrix, const UIntPair& worldPos) 
{
    int rows1 = (int)numRows() ;
    int cols1 = (int)numCols() ;

    int rows2 = (int) matrix.numRows() ;
    int cols2 = (int) matrix.numCols() ;

    int residueRow = rows1 - (int)worldPos.get<0>() ;
    int residueCol = cols1 - (int)worldPos.get<1>() ;

    if (residueRow < rows2 || residueCol < cols2) {
        unsigned int rowBound = rows2 - residueRow > 0 ? rows2 - residueRow : 0 ;
        unsigned int colBound = cols2 - residueCol > 0 ? cols2 - residueCol : 0 ;

        UIntPair exceptionCoord = boost::make_tuple(rowBound, colBound) ;
        
        throw BindException(exceptionCoord) ;
    }

    int transMat1[3][3], transMat2[3][3] ;

    getInverseTransformMat(transMat1) ;
    matrix.getInverseTransformMat(transMat2) ;

    int i1 = (int)worldPos.get<0>() ;
    int j1 = (int)worldPos.get<1>() ;
    int i2, j2 ;

    for(i2 = 0; i1 < rows1 && i2 < rows2; ++i1, ++i2) {
        j1 = (int)worldPos.get<1>() ;
        j2 = 0 ;
        for(; j1 < cols1 && j2 < cols2; ++j1, ++j2) {
  	    IntPair curCoord1 = boost::make_tuple(i1, j1) ;        
	    IntPair matCoord1 = getMatrixCoord(curCoord1, transMat1) ;

  	    IntPair curCoord2 = boost::make_tuple(i2, j2) ;        
	    IntPair matCoord2 = getMatrixCoord(curCoord2, transMat2) ;

	    assert(matCoord1.get<0>() >= 0 && matCoord1.get<1>() >= 0) ;
	    assert(matCoord2.get<0>() >= 0 && matCoord2.get<1>() >= 0) ;

            if (m_data[matCoord1.get<0>()][matCoord1.get<1>()] == 1 &&
		matrix.m_data[matCoord2.get<0>()][matCoord2.get<1>()] == 1) {
  	        UIntPair exceptionCoord = boost::make_tuple((unsigned int)matCoord1.get<0>(),
		    				            (unsigned int)matCoord1.get<1>()) ;
  	        throw BindException(exceptionCoord) ;
	    }

            if (matrix.m_data[matCoord2.get<0>()][matCoord2.get<1>()] == 1)
	        m_data[matCoord1.get<0>()][matCoord1.get<1>()] = true ;
        }
    }
    return ;
}

/*
 * MatrixModel : isBindingPossibleAt (public member function, non-const)
 * Args        : matrix   : The matrix whose elements need to be applied/extracted on the
 *                          current matrix model.
 *               worldPos : worldPos Pos of the current matrix (in WORLD POS and not
 *                          in MATRIX POS).
 *               reverse  : If this flag is set, then operation being is sought is extraction.
 * Returns     : bool
 *               true  - if binding possible without breaking overlap constraint
 *               false - if overlap constraint is not satisfied.
 * Throws      : InvalidOrientationException (through getInverseTransformMat)
 * Defn        :
 *               Checks if mapping the input matrx at worldPos is possible, such that the (0,0)
 *               of the input matrix is at worldPos of the current matrix.
 * Algo        :
 *               1. Calculate the available space on the right and bottom of the current matrix
 *                  starting from worldPos. (residueRow, residueCol)
 *               2. If (residueRow < (rowCnt of inputMatrix)) or
 *                     (residueCol < (colCnt of inputMatrix))
 *                     return false
 *               3. Iterate inputMatrix form (0,0) to (rowCnt, colCnt of inputMatrix)
 *                  Iterate currentMatrix form (worldPos) to (rowCnt, colCnt of currentMatrix)
 *               4. Get the equivalent MatrixPos coords of the coords got at step 3
 *               5a. If there is a true val at the coord calculated at step 3 in input matrix and
 *                   also there is a true val at the coord calculated for current matrix at
 *                   step 3 return false. (For Mapping, reverse = false)
 *               5b. If there is a false val at the coord calculated in step 3 in
 *                   currentMatrix and there is a true val at the coord calculated in step 3
 *                   in inputMatrix then return
 *                   false. (For Unmapping, reverse = true)
 *               6. Once the iteration is over return true, as no overlap constraint is violated
 */ 
bool
MatrixModel::isBindingPossibleAt(const MatrixModel& matrix, const UIntPair& worldPos,
                                 bool reverse)  const
{
    int rows1 = (int)numRows() ;
    int cols1 = (int)numCols() ;

    int rows2 = (int) matrix.numRows() ;
    int cols2 = (int) matrix.numCols() ;

    int residueRow = rows1 - (int)worldPos.get<0>() ;
    int residueCol = cols1 - (int)worldPos.get<1>() ;

    if (residueRow < rows2 || residueCol < cols2) 
        return false ;

    int transMat1[3][3], transMat2[3][3] ;

    getInverseTransformMat(transMat1) ;
    matrix.getInverseTransformMat(transMat2) ;

    int i1 = (int)worldPos.get<0>() ;
    int j1 = (int)worldPos.get<1>() ;
    int i2, j2 ;

    for(i2 = 0; i1 < rows1 && i2 < rows2; ++i1, ++i2) {
        j1 = (int)worldPos.get<1>() ;
        j2 = 0 ;
        for(; j1 < cols1 && j2 < cols2; ++j1, ++j2) {
  	    IntPair curCoord1 = boost::make_tuple(i1, j1) ;         
	    IntPair matCoord1 = getMatrixCoord(curCoord1, transMat1) ;  

  	    IntPair curCoord2 = boost::make_tuple(i2, j2) ;        
	    IntPair matCoord2 = getMatrixCoord(curCoord2, transMat2) ; 

	    assert(matCoord1.get<0>() >= 0 && matCoord1.get<1>() >= 0) ;
	    assert(matCoord2.get<0>() >= 0 && matCoord2.get<1>() >= 0) ;

            if (reverse && m_data[matCoord1.get<0>()][matCoord1.get<1>()] == 0 &&
                matrix.m_data[matCoord2.get<0>()][matCoord2.get<1>()] == 1)
  	        return false ;
            if (!reverse && 
		matrix.m_data[matCoord2.get<0>()][matCoord2.get<1>()] == 1 && 
		m_data[matCoord1.get<0>()][matCoord1.get<1>()] == 1) 
 	        return false ;
        }
    }
    return true ;
}

/*
 * MatrixModel : unbindMatrixFrom (public member function, non-const)
 * Args        : matrix   : The matrix whose elements need to be extracted from the
 *                          current matrix model.
 *               worldPos : worldPos Pos of the current matrix (in WORLD POS and not
 *                          in MATRIX POS), from where the extraction op is to start.
 * Returns     : Nothing
 * Throws      : BindException, InvalidOrientationException (through getInverseTransformMat)
 * Defn        :
 *               Extracts input matrix from worldPos, such that the (0,0)
 *               of the input matrix is at worldPos of the current matrix.
 * Algo        :
 *               1. Calculate the available space on the right and bottom of the current matrix
 *                  starting from worldPos. (residueRow, residueCol)
 *               2. If (residueRow < (rowCnt of inputMatrix)) or
 *                     (residueCol < (colCnt of inputMatrix))
 *                     return false
 *               3. Iterate inputMatrix form (0,0) to (rowCnt, colCnt of inputMatrix)
 *                  Iterate currentMatrix form (worldPos) to (rowCnt, colCnt of currentMatrix)
 *               4. Get the equivalent MatrixPos coords of the coords got at step 3
 *               5. If there is a false val at the coord calculated in step 3 in
 *                  currentMatrix and there is a true val at the coord calculated in
 *                  step 4 in inputMatrix then throw bind exception. Else if the
 *                  currentMatrix have 1 at pos calculated at step 4 and input matrix also
 *                  has 1 at pos calculated at step 4, set false to the current matrix at
 *                  this coord.
 */ 
void
MatrixModel::unbindMatrixFrom(const MatrixModel& matrix, const UIntPair& worldPos) 
{
    int rows1 = (int)numRows() ;
    int cols1 = (int)numCols() ;

    int rows2 = (int) matrix.numRows() ;
    int cols2 = (int) matrix.numCols() ;

    int residueRow = rows1 - (int)worldPos.get<0>() ;
    int residueCol = cols1 - (int)worldPos.get<1>() ;

    if (residueRow < rows2 || residueCol < cols2) {
        unsigned int rowBound = rows2 - residueRow > 0 ? rows2 - residueRow : 0 ;
        unsigned int colBound = cols2 - residueCol > 0 ? cols2 - residueCol : 0 ;
        
	UIntPair exceptionCoord = boost::make_tuple(rowBound, colBound) ;
        throw BindException(exceptionCoord) ;
    }

    int transMat1[3][3], transMat2[3][3] ;

    getInverseTransformMat(transMat1) ;
    matrix.getInverseTransformMat(transMat2) ;

    int i1 = (int)worldPos.get<0>() ;
    int j1 = (int)worldPos.get<1>() ;
    int i2, j2 ;

    for(i2 = 0; i1 < rows1 && i2 < rows2; ++i1, ++i2) {
        j1 = (int)worldPos.get<1>() ;
        j2 = 0 ;
        for(; j1 < cols1 && j2 < cols2; ++j1, ++j2) {
  	    IntPair curCoord = boost::make_tuple(i1, j1) ;  
	    IntPair matCoord1 = getMatrixCoord(curCoord, transMat1) ; 
	    assert(matCoord1.get<0>() >= 0 && matCoord1.get<1>() >= 0) ;

            curCoord = boost::make_tuple(i2, j2) ;
            IntPair matCoord2 = getMatrixCoord(curCoord, transMat2) ;

	    assert(matCoord2.get<0>() >= 0 && matCoord2.get<1>() >= 0) ;
            if (m_data[matCoord1.get<0>()][matCoord1.get<1>()] == 0 &&
                matrix.m_data[matCoord2.get<0>()][matCoord2.get<1>()] == 1) {
 	        UIntPair exceptionCoord = boost::make_tuple((unsigned int)i1, (unsigned int)j1) ;
  	        throw UnbindException(exceptionCoord) ;
	    }
            if (matrix.m_data[matCoord2.get<0>()][matCoord2.get<1>()] == 1)
                m_data[matCoord1.get<0>()][matCoord1.get<1>()] = 0 ;
        }
    }
    return ;
}

/*
 * MatrixModel : isAnyBitSet (public const member function)
 * Args        : None
 * Returns     : bool
 *               true  - if any bit is set in the matrix model.
 *               false - if none of the bit is set in matrix
 * Throws      : Nothing
 * Defn        :
 *               Iterate upon each row of the matrix and returns true if a true val
 *               is found at any index of the 2D matrix(dynamic_bitset), else return false.
 */ 
bool
MatrixModel::isAnyBitSet() const
{
    for(unsigned int i = 0 ; i < m_dimension.get<0>(); ++i) {
        if (m_data[i].any())
	    return true ;
    }
    return false ;
}

/*
 * MatrixModel : clearModel (public non-const member function)
 * Args        : None
 * Returns     : Nothing
 * Throws      : Nothing
 * Defn        :
 *               Iterate upon each row of the matrix and issue a clear call
 *               for dynamic_bitset of the row.
 */ 
void
MatrixModel::clearModel()
{
    for(unsigned int i = 0 ; i < m_dimension.get<0>(); ++i) 
        (void)m_data[i].reset() ;
}

/*
 * MatrixModel : findDiffLoc (public const member function.)
 * Args        : matPos       - ref variable which will be populated if a diff is found at a loc.
 *               curModelVal  - The value which the current matrix should have at loc
 *                              under consideration
 *               goalModelVal - The value which the goal matrix should have at loc
 *                              under consideration
 *               goalModel    - golaModel Matrix
 *               dir          - row-major or col-major search
 * Returns     : true  - If a desired match is found, the value of the loc is copied in matPos
 *               false - If no desired match is found.
 * Throws      : Nothing
 * Defn        :
 *               1. Iterate upon the raw matrix model and goal matrix model
 *               2. Check if the value at the current coord of raw matrix model matches
 *                  curModelVal and that of goalMatrixModel matches goalModelVal at
 *                  current coord under iteration.
 *               3. If a match is found as desired in step 2, return true else return false.
 * Notes       :
 *               1. If the dir is X_DIR, iterate the matrix in row-major form else in
 *                 column-major form.
 */ 
bool
MatrixModel::findDiffLoc(UIntPair& matPos, bool curModelVal, bool goalModelVal,
			 const MatrixModel& goalModel, DIR dir) const
{
    if (m_dimension.get<0>() != goalModel.m_dimension.get<0>() ||
	m_dimension.get<1>() != goalModel.m_dimension.get<1>() )
        return false ;
    if (dir == X_DIR) {
        for(unsigned int i = 0; i < m_dimension.get<0>(); ++i) {
            for(unsigned int j = 0; j < m_dimension.get<1>(); ++j) {
                if (goalModel.m_data[i][j] == goalModelVal && m_data[i][j] == curModelVal) {
                    boost::get<0>(matPos) = i ;
                    boost::get<1>(matPos) = j ;
                    return true ;
                }
            }
        }
    }
    else if (Y_DIR) {
        for(unsigned int j = 0; j < m_dimension.get<1>(); ++j) {
            for(unsigned int i = 0; i < m_dimension.get<0>(); ++i) {
                if (goalModel.m_data[i][j] == goalModelVal && m_data[i][j] == curModelVal) {
                    boost::get<0>(matPos) = i ;
                    boost::get<1>(matPos) = j ;
                    return true ;
                }
            }
        }        
    }
    return false ;
}

/*
 * MatrixModel : shiftNeededToGetValAtTopLeft (public const member function.)
 * Args        : val          - value which is desired at top-left i..e (0,0)
 *               shift        - Amount by which matrix model needs to be shifted left to
 *                              get value at (0,0) = val
 *               dir          - Shift direct, if X_DIR = Left else if Y_DIR = top
 * Returns     : true  - If a desired match is found, the value of the loc is copied in matPos
 *               false - If no desired match is found.
 * Throws      : InvalidOrientationException (through getInverseTransformMat)
 * Defn        :
 *               1. initialize variable shift to 0, and iterate upon the raw matrix model
 *                  with row = 0 
 *                  for X_DIR and col = 0 for Y_DIR.
 *               2. Get the inverse transformation matrix.
 *               3. Get the equivalent matrix-coord for current world-coord of iteration.
 *               2. Check if the value at the current matrix-coord of matrix model matches 'val'
 *               3. If a match is found as desired in step 2, return the current value of
 *                  shift, otherwise increment shift and continue iteration.
 * Notes       :
 *               1. If the dir is X_DIR, iterate the matrix for every col after
 *                  setting row to 0(row will not be incremented)
 *               2. If the dir is Y_DIR, iterate the matrix for every row after
 *                  setting col to 0(col will not be incremented)
 *               3. Iteration doesnt happen on exact dimension of the matrix but
 *                  dimension got after using numRows/numCols which takes into consideration
 *                  the orientation.(Thats why step3 is used in algo)
 */ 
bool
MatrixModel::shiftNeededToGetValAtTopLeft(bool val, DIR dir, unsigned int& shift) const
{
    int transformMat[3][3] ;
    shift = 0 ;
    
    getInverseTransformMat(transformMat) ;
    
    if (dir == X_DIR) {
        unsigned int c = 0 ;
        unsigned int colCnt = numCols() ;
        for(; c < colCnt; ++c, ++shift) {
            IntPair curCoord = boost::make_tuple((int)0, (int)c) ;
            IntPair newCoord = getMatrixCoord(curCoord, transformMat) ;
            if (m_data[newCoord.get<0>()][newCoord.get<1>()] == val)
                return true ;
        }
    } else if (dir == Y_DIR) {
        unsigned int r = 0 ;
        unsigned int rowCnt = numRows() ;
        for(; r < rowCnt; ++r, ++shift) {
            IntPair curCoord = boost::make_tuple((int)r, (int)0) ;
            IntPair newCoord = getMatrixCoord(curCoord, transformMat) ;
            if (m_data[newCoord.get<0>()][newCoord.get<1>()] == val)
                return true ;
        }
    }
    return false ;
}

/*
 * MatrixModel : initialize (public non-const member function.)
 * Args        : row   - row count of the matrix model
 *               col   - col count of the matrix
 * Returns     : Nothing
 * Throws      : Nothing
 * Defn        :
 *               1. Clear the old value of the matrix
 *               2. Initialize the dimension of the matrix with (row, col)
 *               3. Initilaize each row of the matrix with dynmaic_bitset of size col.
 *               4. Set the orientation as R0
 */ 
void
MatrixModel::initialize(unsigned int row, unsigned int col)
{
    m_dimension.get<0>() = row ;
    m_dimension.get<1>() = col ;
    
    m_data.reserve(row) ;
    m_data.insert(m_data.begin(), row, boost::dynamic_bitset<>(col)) ;

    m_orient = R0 ;
    return ;
}

/*
 * MatrixModel : printModelWithChar (public const member function.)
 * Args        : char ch  - The char which needs to be present at thos locs
 *                          where matrix contains true
 * Returns     : Nothing
 * Throws      : InvalidOrientationException (through getInverseTransformMat)
 * Defn        :
 *               print char 'ch' for true posns of matrix and '0' for false.
 */ 
void
MatrixModel::printModelWithChar(char ch) const
{
    unsigned int row = numRows() ;
    unsigned int col = numCols() ;
    int transformMat[3][3] ;
    getInverseTransformMat(transformMat) ;

    for(int i = 0; i < (int)row; ++i) {
        for(int j = 0; j < (int)col; ++j) {
	    // (i,j) is worldCoord.
  	    IntPair curCoord = boost::make_tuple(i, j) ;  
	    IntPair matCoord = getMatrixCoord(curCoord, transformMat) ; 
	    assert(matCoord.get<0>() >= 0 && matCoord.get<1>() >= 0) ;
   	    if (m_data[matCoord.get<0>()][matCoord.get<1>()]) 
	        std::cout << ch;
            else 
	        std::cout << '0';
	}
	std::cout <<std::endl ;
    }
}

//static
IntPair
MatrixModel::getMatrixCoord(const IntPair& worldCoord, const int transMat[][3])
{
    IntPair actCoord = boost::make_tuple(worldCoord.get<1>(),
                                         worldCoord.get<0>() * -1) ;
    IntPair tmpCoord = matrixMult(transMat, actCoord) ;
    return boost::make_tuple(tmpCoord.get<1>() * -1,
                             tmpCoord.get<0>()) ;
}

/*
 * MatrixModel : applyInverseTransformToWorld (private const member function.)
 * Args        : worldCoord  - Transformed World-Coord of the matrix.
 * Returns     : matrixCoord - Equivalent matrix coord of the raw matrix model.
 * Throws      : InvalidOrientationException (through getInverseTransformMat)
 * Defn        :
 *               1. Get the inverse transformation matrix for the curret orientation.
 *               2. apply transformation matrix to get the equivalent matrix-coord of
 *                  raw matrix model.
 * Notes       :
 *               As the transformation matrix contains -ve elements as well, hence the
 *               current coord is typecasted to integer coord. Also by design the final
 *               result will never be -ve hence assertion.
 */ 
UIntPair
MatrixModel::applyInverseTransformToWorld(const UIntPair& worldCoord) const
{
    int transformMat[3][3] ;
    getInverseTransformMat(transformMat) ;
    IntPair newCoord = MatrixModel::getMatrixCoord(worldCoord, transformMat) ;

    assert(newCoord.get<0>() >= 0 && newCoord.get<1>() >=0) ;
    return boost::make_tuple((unsigned int)newCoord.get<0>(),
                             (unsigned int)newCoord.get<1>()) ;    
}

/*
 * MatrixModel : matrixMult (private const member function.)
 * Args        : mat   - transformation (3X3 integer matrix)
 *             : coord - coord vector 
 * Returns     : transformed coord
 * Throws      : Nothing
 * Defn        :
 *               1. return the result of mnatrix*vector multiplication
 * Notes       :
 *               As the transformation matrix is of size 3X3 and vector is just 2X1
 *               addition row is assumed to be present with value = 1
 */
//static
IntPair
MatrixModel::matrixMult(const int mat[3][3], const IntPair& coord) 
{
  return boost::make_tuple(mat[0][0] * coord.get<0>() + mat[0][1] * coord.get<1>() + mat[0][2],
			   mat[1][0] * coord.get<0>() + mat[1][1] * coord.get<1>() + mat[1][2]) ;
}

/*
 * MatrixModel : matrixMult (private const member function.)
 * Args        : mat1   - 3X3 integer matrix
 *             : mat2   - 3X3 integer matrix
 *             : resMat - 3X3 ref integer matrix
 * Returns     : Nothing (resMat is poulated)
 * Throws      : Nothing
 * Defn        :
 *               1. Stores the result of mat1 * mat2 in resMat
 */
//static
void
MatrixModel::matrixMult(const int mat1[3][3], const int mat2[3][3], int resMat[3][3]) 
{
    resMat[0][0] = mat1[0][0] * mat2[0][0] + mat1[0][1] * mat2[1][0] + mat1[0][2] * mat2[2][0] ;
    resMat[0][1] = mat1[0][0] * mat2[0][1] + mat1[0][1] * mat2[1][1] + mat1[0][2] * mat2[2][1] ;
    resMat[0][2] = mat1[0][0] * mat2[0][2] + mat1[0][1] * mat2[1][2] + mat1[0][2] * mat2[2][2] ;

    resMat[1][0] = mat1[1][0] * mat2[0][0] + mat1[1][1] * mat2[1][0] + mat1[1][2] * mat2[2][0] ;
    resMat[1][1] = mat1[1][0] * mat2[0][1] + mat1[1][1] * mat2[1][1] + mat1[1][2] * mat2[2][1] ;
    resMat[1][2] = mat1[1][0] * mat2[0][2] + mat1[1][1] * mat2[1][2] + mat1[1][2] * mat2[2][2] ;

    resMat[2][0] = mat1[2][0] * mat2[0][0] + mat1[2][1] * mat2[1][0] + mat1[2][2] * mat2[2][0] ;
    resMat[2][1] = mat1[2][0] * mat2[0][1] + mat1[2][1] * mat2[1][1] + mat1[2][2] * mat2[2][1] ;
    resMat[2][2] = mat1[2][0] * mat2[0][2] + mat1[2][1] * mat2[1][2] + mat1[2][2] * mat2[2][2] ;
 
    return ;
}

/*
 * MatrixModel : getInverseTransformMat (private const member function.)
 * Args        : transformMat - 3X3 integer matrix, to be populated by the function with current 
 *                              inverse transform matrix.
 * Returns     : Nothing (transformMat is poulated)
 * Throws      : InvalidOrientationException
 * Defn        :
 *               1. Depeneding upon the orientation of the matrix, populate the transform Mat.
 * Notes       : Look into affine-transformation fro 2D in computer graphics...
 *               The intial R0 model needs to be placed at 4th quadrant such that (0,0)
 *               of the matrix is at the origin. We have used this approach, as this is
 *               the way the matrix is modelled in computer.
 *                                            |
 *                                            |
 *                                    2nd Q   |    Ist Q
 *                                            |
 *                                ---------------------------
 *                                            |(0,0)     |
 *                                    3rd Q   |  Matrix  | 4th Q
 *                                            |          |
 *                                            |__________|
 *                                            |
 *        Transformation :
 *               1. After applying rotational/flip transformations for various
 *                  orientations the matrix is pulled to the 4th Quadrant using translational
 *                  operations.
 *
 *               2. To get the inverse transformation all the operations which were
 *                  applied in the previous step is applied in reverse.
 */
void
MatrixModel::getInverseTransformMat(int transformMat[3][3]) const
{
    switch(m_orient)
    {
        case R0 :
  	    return getR0InverseTransformMat(transformMat) ;
        case R90 :
  	    return getR90InverseTransformMat(transformMat) ;
        case R180 :
  	    return getR180InverseTransformMat(transformMat) ;
        case R270 :
  	    return getR270InverseTransformMat(transformMat) ;
        case FR0 :
  	    return getFR0InverseTransformMat(transformMat) ;
        case FR90 :
  	    return getFR90InverseTransformMat(transformMat) ;
        case FR180 :
  	    return getFR180InverseTransformMat(transformMat) ;
        case FR270 :
  	    return getFR270InverseTransformMat(transformMat) ;
        default :
	    throw InvalidOrientationException(m_orient) ;
  	    break ;
    }
}

/*
 * MatrixModel : getR0InverseTransformMat (private const member function.)
 * Args        : transformMat - 3X3 integer matrix, to be populated by the function with current 
 *                              inverse transform matrix.
 * Returns     : Nothing (transformMat is poulated)
 * Throws      : Nothing
 * Defn        :
 *               1. Identity matrix as raw-matrix model is in R0 orientation.
 */
void 
MatrixModel::getR0InverseTransformMat(int transformMat[3][3]) const
{
    transformMat[0][0] = transformMat[1][1] = transformMat[2][2] = 1 ;
    transformMat[0][1] = transformMat[0][2] = transformMat[1][0] =
        transformMat[1][2] = transformMat[2][0] = transformMat[2][1] = 0 ;
    return ;
}

/*
 * MatrixModel : getR90InverseTransformMat (private const member function.)
 * Args        : transformMat - 3X3 integer matrix, to be populated by the function with R90
 *                              inverse transform matrix.
 * Returns     : Nothing (transformMat is poulated)
 * Throws      : Nothing
 * Defn        : 
 *               Initialize Translation and Rotation matrices with constant terms.
 *               1. Translate model with (Tx = -1 * row, Ty = 0)
 *               2. Rotate model with (Angle = -90)
 *               3. Transformation = (rotateMat * translateMat)
 */
void
MatrixModel::getR90InverseTransformMat(int transformMat[3][3]) const
{
    int translateMat[3][3] ;
    initTranslateMat(translateMat) ;
    translateMat[0][2] = -1 * (m_dimension.get<0>() - 1) ;
    translateMat[1][2] = 0 ;

    int rotateMat[3][3] ;
    initRotateMat(rotateMat) ;
    rotateMat[0][0] = rotateMat[1][1] = CosMinusTheta * COS90 ;
    rotateMat[0][1] = SinMinusTheta * SIN90 ;
    rotateMat[1][0] = -1 * SinMinusTheta * SIN90 ;

    matrixMult(rotateMat, translateMat, transformMat) ;
    return ;
}

/*
 * MatrixModel : getR180InverseTransformMat (private const member function.)
 * Args        : transformMat - 3X3 integer matrix, to be populated by the function with R180
 *                              inverse transform matrix.
 * Returns     : Nothing (transformMat is poulated)
 * Throws      : Nothing
 * Defn        :
 *               Initialize Translation and Rotation matrices with constant terms.
 *               1. Translate model with (Tx = -1 * (col - 1), Ty = (row - 1))
 *               2. Rotate model with (Angle = -180)
 *               3. Transformation = (rotateMat * translateMat)
 */
void
MatrixModel::getR180InverseTransformMat(int transformMat[3][3]) const
{
    int translateMat[3][3] ;
    initTranslateMat(translateMat) ;
    translateMat[0][2] = -1 * (m_dimension.get<1>() - 1) ;
    translateMat[1][2] = (m_dimension.get<0>() - 1) ;

    int rotateMat[3][3] ;
    initRotateMat(rotateMat) ;
    rotateMat[0][0] = rotateMat[1][1] = CosMinusTheta * COS180 ;
    rotateMat[0][1] = SinMinusTheta * SIN180 ;
    rotateMat[1][0] = -1 * SinMinusTheta * SIN180 ;

    matrixMult(rotateMat, translateMat, transformMat) ;
    return ;    
}

/*
 * MatrixModel : getR270InverseTransformMat (private const member function.)
 * Args        : transformMat - 3X3 integer matrix, to be populated by the function with R270
 *                              inverse transform matrix.
 * Returns     : Nothing (transformMat is poulated)
 * Throws      : Nothing
 * Defn        :
 *               Initialize Translation and Rotation matrices with constant terms.
 *               1. Translate model with (Tx = 0, Ty = (col - 1))
 *               2. Rotate model with (Angle = -270)
 *               3. Transformation = (rotateMat * translateMat)
 */
void
MatrixModel::getR270InverseTransformMat(int transformMat[3][3]) const
{
    int translateMat[3][3] ;
    initTranslateMat(translateMat) ;
    translateMat[0][2] = 0 ;
    translateMat[1][2] = m_dimension.get<1>() - 1 ;

    int rotateMat[3][3] ;
    initRotateMat(rotateMat) ;
    rotateMat[0][0] = rotateMat[1][1] = CosMinusTheta * COS270 ;
    rotateMat[0][1] = SinMinusTheta * SIN270 ;
    rotateMat[1][0] = -1 * SinMinusTheta * SIN270 ;

    matrixMult(rotateMat, translateMat, transformMat) ;
    return ;
}

/*
 * MatrixModel : getFR0InverseTransformMat (private const member function.)
 * Args        : transformMat - 3X3 integer matrix, to be populated by the function with FR0
 *                              inverse transform matrix.
 * Returns     : Nothing (transformMat is poulated)
 * Throws      : Nothing
 * Defn        :
 *               Initialize Translation and Flip matrices with constant terms.
 *               1. Translate the Model (Tx = 0, Ty = (rows - 1)
 *               2. Flip the Y coord of the Model
 *               3. Transformation = flipYMat * translateMate
 */
void 
MatrixModel::getFR0InverseTransformMat(int transformMat[3][3]) const
{
    int flipYMat[3][3] ;
    initFlipMat(flipYMat) ;
    flipYMat[1][1] = -1 ;
    flipYMat[0][0] = 1 ;

    int translateMat[3][3] ;
    initTranslateMat(translateMat) ;
    translateMat[0][2] = 0 ;
    translateMat[1][2] = m_dimension.get<0>() - 1 ;

    matrixMult(flipYMat, translateMat, transformMat) ;
    return ;
}

/*
 * MatrixModel : getFR90InverseTransformMat (private const member function.)
 * Args        : transformMat - 3X3 integer matrix, to be populated by the function with FR90
 *                              inverse transform matrix.
 * Returns     : Nothing (transformMat is poulated)
 * Throws      : Nothing
 * Defn        :
 *               Initialize Flip and Rotation matrices with constant terms.
 *               1. Flip the Y coord of the Model
 *               2. Rotate the model with (Angle = -90)
 *               2. Transformation = flipYMat * rotateMate
 */
void 
MatrixModel::getFR90InverseTransformMat(int transformMat[3][3]) const
{
    int flipYMat[3][3] ;
    initFlipMat(flipYMat) ;
    flipYMat[1][1] = -1 ;
    flipYMat[0][0] = 1 ;

    int rotateMat[3][3] ;
    initRotateMat(rotateMat) ;
    rotateMat[0][0] = rotateMat[1][1] = CosMinusTheta * COS90 ;
    rotateMat[0][1] = SinMinusTheta * SIN90 ;
    rotateMat[1][0] = -1 * SinMinusTheta * SIN90 ;

    matrixMult(flipYMat, rotateMat, transformMat) ;
    return ;
}

/*
 * MatrixModel : getFR180InverseTransformMat (private const member function.)
 * Args        : transformMat - 3X3 integer matrix, to be populated by the function with FR180
 *                              inverse transform matrix.
 * Returns     : Nothing (transformMat is poulated)
 * Throws      : Nothing
 * Defn        :
 *               Initialize Flip Translation and Rotation matrices with constant terms.
 *               1. Translate the model with (Tx = -1 * (cols - 1))
 *               2. Rotate the model with (Angle = -180)
 *               3. Flip the Y coord of the Model
 *               4. Transformation = flipYMat * rotateMate * translateMat 
 */
void
MatrixModel::getFR180InverseTransformMat(int transformMat[3][3]) const
{
    int flipYMat[3][3] ;
    initFlipMat(flipYMat) ;
    flipYMat[0][0] = 1 ;
    flipYMat[1][1] = -1 ;

    int translateMat[3][3] ;
    initTranslateMat(translateMat) ;
    translateMat[0][2] = -1 * (m_dimension.get<1>() - 1) ;
    translateMat[1][2] = 0 ;

    int rotateMat[3][3] ;
    initRotateMat(rotateMat) ;
    rotateMat[0][0] = rotateMat[1][1] = CosMinusTheta * COS180 ;
    rotateMat[0][1] = SinMinusTheta * SIN180 ;
    rotateMat[1][0] = -1 * SinMinusTheta * SIN180 ;

    int intermediateMat[3][3] ;
    matrixMult(flipYMat, rotateMat, intermediateMat) ;
    matrixMult(intermediateMat, translateMat, transformMat) ;
    return ;
}

/*
 * MatrixModel : getFR270InverseTransformMat (private const member function.)
 * Args        : transformMat - 3X3 integer matrix, to be populated by the function with FR270
 *                              inverse transform matrix.
 * Returns     : Nothing (transformMat is poulated)
 * Throws      : Nothing
 * Defn        :
 *               Initialize Flip Translation and Rotation matrices with constant terms.
 *               1. Translate the model with (Tx = -1 * (rows - 1), Ty = (cols - 1))
 *               2. Rotate the model with (Angle = -270)
 *               3. Flip the Y coord of the Model
 *               4. Transformation = flipYMat * rotateMate * translateMat 
 */
void
MatrixModel::getFR270InverseTransformMat(int transformMat[3][3]) const
{
    int flipYMat[3][3] ;
    initFlipMat(flipYMat) ;
    flipYMat[0][0] = 1 ;
    flipYMat[1][1] = -1 ;

    int translateMat[3][3] ;
    initTranslateMat(translateMat) ;
    translateMat[0][2] = -1 * (m_dimension.get<0>() - 1) ;
    translateMat[1][2] = m_dimension.get<1>() - 1 ;

    int rotateMat[3][3] ;
    initRotateMat(rotateMat) ;
    rotateMat[0][0] = rotateMat[1][1] = CosMinusTheta * COS270 ;
    rotateMat[0][1] = SinMinusTheta * SIN270 ;
    rotateMat[1][0] = -1 * SinMinusTheta * SIN270 ;

    int intermediateMat[3][3] ;
    matrixMult(flipYMat, rotateMat, intermediateMat) ;
    matrixMult(intermediateMat, translateMat, transformMat) ;
    return ;
}

/*
 * MatrixModel : doCurTransformedValCompare (private const member function.)
 * Args        : 
 *               MatrixModel matrix : The matrix with which comparison needs to be performed.
 * Returns     : bool 
 *             :   true - If the current transformed matrix is equal to the
 *                        non-transformed input matrix.
 * Throws      : InvalidOrientationException(through getInverseTransformMat)
 * Defn        : Compare the current matrix with input matrix.(Input matrtix is assumed
 *               to be in R0 orientation no matter what orientation it is in, whereas
 *               the current matrix takes its orientation into consideration.
 * Algo        :
 *               1. If the transformed dimension of the current matrix is not equal to
 *                  the original dimension of the input matrix return false.
 *               2. Get the inverse transform matrix of the current matrix
 *               3. Iterate upon the transformed dimension of the current matrix and
 *                  original dimension of the input matrix.
 *               4. Transform the coord of the current matrix and compare with
 *                  the current element of input matrix.
 *               5. If the comparison failed at step 4, return false, else continue iteration.
 *               6. return true post ietration complete.
 */
bool
MatrixModel::doCurTransformedValCompare(const MatrixModel& matrix) const
{
    unsigned int rows1 = numRows() ;   
    unsigned int cols1 = numCols() ;   

    unsigned int rows2 = matrix.m_dimension.get<0>() ;
    unsigned int cols2 = matrix.m_dimension.get<1>() ;

    if (rows1 != rows2 || cols1 != cols2)
        return false ;

    int transformMat[3][3] ;
    getInverseTransformMat(transformMat) ;

    for(int i = 0; i < (int)rows1; ++i) {
      for (int j = 0 ; j < (int)cols1; ++j) {
  	    IntPair curCoord = boost::make_tuple(i, j) ;
            IntPair matCoord = getMatrixCoord(curCoord, transformMat) ;
  	    if (m_data[matCoord.get<0>()][matCoord.get<1>()] != matrix.m_data[i][j])
	        return false ;
        }
    }
    return true ;
}

/*
 * MatrixModel : doTransformedValCompare (private const member function.)
 * Args        : 
 *               MatrixModel matrix : The matrix with which comparison needs to be performed.
 * Returns     : bool 
 *             :   true - If the current transformed matrix is equal to the transformed input
 *                        matrix.
 * Throws      : InvalidOrientationException(through getInverseTransformMat)
 * Defn        : Compare the current matrix with input matrix.
 * Algo        :
 *               1. If the transformed dimension of the current matrix is not equal to the
 *                  transformed dimension of the input matrix return false.
 *               2. Get the inverse transform matrices of the current matrix and input matrix.
 *               3. Iterate upon the transformed dimension of the current matrix and
 *                  transformed dimension of the input matrix.
 *               4. Transform the coord of the current matrix and compare with the transformed
 *                  element of input matrix.
 *               5. If the comparison failed at step 4, return false, else continue iteration.
 *               6. return true post ietration complete.
 */
bool
MatrixModel::doTransformedValCompare(const MatrixModel& matrix) const
{
    int transformMat1[3][3] ;
    getInverseTransformMat(transformMat1) ;

    int transformMat2[3][3] ;
    matrix.getInverseTransformMat(transformMat2) ;

    unsigned int rows1 = numRows() ;   
    unsigned int cols1 = numCols() ;   

    unsigned int rows2 = matrix.numRows() ;
    unsigned int cols2 = matrix.numCols() ;

    if (rows1 != rows2 || cols1 != cols2)
        return false ;
    for(int i = 0; i < (int)rows1; ++i) {
        for (int j = 0 ; j < (int)cols1; ++j) {
  	    IntPair curCoord = boost::make_tuple(i, j) ;
            IntPair matCoord1 = getMatrixCoord(curCoord, transformMat1) ;
            IntPair matCoord2 = getMatrixCoord(curCoord, transformMat2) ;
  	    if (m_data[matCoord1.get<0>()][matCoord1.get<1>()] !=
                matrix.m_data[matCoord2.get<0>()][matCoord2.get<1>()])
	        return false ;
        }
    }
    return true ;
}

/*
 * MatrixModel : initTranslateMat (private const member function.)
 * Args        : transformMat - 3X3 integer matrix, to be populated by the function with
 *                              constants of translation matrix.
 * Returns     : Nothing (transformMat is poulated)
 * Throws      : Nothing
 * Defn        :
 *               The indices which always contains constants for translation are populated here
 *                                [ 1  0  tx ]
 *                translateMat =  | 0  1  ty |
 *                                [ 0  0  1  ]
 */
void
MatrixModel::initTranslateMat(int transMat[3][3]) const
{
    transMat[0][0] = transMat[1][1] = transMat[2][2] = 1 ;
    transMat[0][1] = transMat[1][0] = transMat[2][0] = transMat[2][1] = 0 ;
    return ;
}

/*
 * MatrixModel : initRotateMat (private const member function.)
 * Args        : transformMat - 3X3 integer matrix, to be populated by the function with
 *                              constants of rotation matrix.
 * Returns     : Nothing (transformMat is poulated)
 * Throws      : Nothing
 * Defn        :
 *               The indices which always contains constants for rotation are populated here
 *                                [ cos(x)  sin(x)  0 ]
 *                rotateMat    =  | -sin(x) cos(x)   0 |
 *                                [ 0       0        1 ]
 */
void
MatrixModel::initRotateMat(int rotMat[3][3]) const
{
    rotMat[2][0] = rotMat[2][1] = rotMat[0][2] = rotMat[1][2] = 0 ;
    rotMat[2][2] = 1 ;
}

/*
 * MatrixModel : initFlipMat (private const member function.)
 * Args        : transformMat - 3X3 integer matrix, to be populated by the function with
 *                              constants of flip matrix.
 * Returns     : Nothing (transformMat is poulated)
 * Throws      : Nothing
 * Defn        :
 *               The indices which always contains constants for flip are populated here
 *                                [ fx  0  0 ]
 *                flipMat      =  | 0  fy  0 |
 *                                [ 0  0   1 ]
 *               Note : for flip in X fx = -1, and for flip in Y, fy = -1
 */
void
MatrixModel::initFlipMat(int flipMat[3][3]) const
{
    flipMat[0][1] = flipMat[0][2] = flipMat[1][0] = flipMat[1][2] = flipMat[2][0] = flipMat[2][1] = 0 ;
    flipMat[2][2] = 1 ;
}

// Implementation of PentominoesModel...

/*
 * PentominoesModel : Constructor   (public)
 * Args             : dimension : Dimension of the model as UIntPair
 *                    goalVal   : Current model is goalModel or not.
 * Returns          : Constructed PentominoesModel object...
 * Throws           : Nothing
 * Defn             :
 *                    Builds a PentominoesModel of the size passed as argument. The first item
 *                    of the pair is treated as count of rows and second as column. 
 *
 *                    The default Base constructor (Model) is called.
 *
 *                   The actual bitMatrix data is modelled in MatrixModel m_data, where each
 *                   row of the matrix is initialized with a dynamic_set with size as no. of
 *                   columns. The dynamic_bitset is initialized with 0(false) for all the rows
 *                   of the matrix. The orientation of the MatrixModel is initialized as R0.
 *          
 *                   Items of the model is intialized as an empty hash_map.
 */
PentominoesModel::PentominoesModel(UIntPair& dimension, bool goalVal) : Model(), p_data(dimension), m_pieces(), 
									m_goalModel(goalVal)
{
}

/*
 * PentominoesModel : Desstructor   (public)
 * Args             : Nothing
 * Returns          : Nothing
 * Throws           : Nothing
 * Defn             :
 *                    Destroys a PentominoesModel, as no direct allocation has happened
 *                    for any memeber variables of the class. no delete is called.
 *
 *                    The Base desstructor (Model) is called automatically.
 */
PentominoesModel::~PentominoesModel() 
{
}

/*
 * PentominoesModel : Overloaded equality operator (operator==)   (public const member function)
 * Args             : const Model : Base class model ref
 * Returns          : bool
 *                    true  - if the current model is equal to the input model.
 *                    false - if the current model is not equal to the input model.
 * Throws           : Nothing (std::bad_cast is handled locally in this function)
 * Defn             :
 *                    The input model is typecasted(dynamic_cast) to PentominoesModel
 *                    and the comparision is done using depp compare, which basically
 *                    tries to be matched with all possible orientation of the model.
 *                    deeepCompare is defined in MatrixModel.
 */
bool
PentominoesModel::operator==(const Model& model) const
{
    try {
        const PentominoesModel &pent_model = dynamic_cast<const PentominoesModel&>(model);
        return p_data.deepCompare(pent_model.p_data) ;
    }
    catch(std::bad_cast& bc) {
        std::cout << "Can't cast Pentominoes Model from the model\n";
    }
    return false ;
}

/*
 * PentominoesModel : lowestEmptyPos (public const member function)
 * Args             : 
 *                    pos : to be populated by the function
 *                    dir : search in row-major or col-major
 * Returns          : bool
 *                    true  - if the current model has a false anywhere.
 *                    false - if the current model has no false anywhere.
 * Throws           : InvalidOrientationException (through MatrixModel::getLowestPosWithVal)
 * Defn             :
 *                    The current 2D bit-matrix model is searched for a false at any index,
 *                    the search is either performed in a row-major or col-major form. 
 * TODO             : Handle the exception locally here as this is the final application using
 *                  : MatrixModel class whose member function is throwing this exception
 */
bool
PentominoesModel::lowestEmptyPos(UIntPair& pos, DIR dir) const
{
    return p_data.getLowestPosWithVal(false, pos, dir) ;
}

/*
 * PentominoesModel : isMappingPossible (public const member function)
 * Args             : 
 *                    mapLoc : Location where the pentominoes piece needs to be placed in
 *                             the crrent matrix model
 *                    pent   : PentominoesPiece which needs to be placed at mapLoc defined above.
 * Returns          : bool
 *                    true  - if the current piece can be placed at the specified loc.
 *                    false - if the current piece cant be placed at the specified loc.
 * Throws           : InvalidOrientationException (through MatrixModel::isBindingPossibleAt)
 * Defn             :
 *                    The check whether the current PentominoesPiece is possible to be placed
 *                    at the mapLoc in the current matrix without breaking overlap exception. 
 * TODO             : Handle the exception locally here as this is the final application using
 *                  : MatrixModel class whose member function is throwing this exception
 */
bool 
PentominoesModel::isMappingPossible(const UIntPair& mapLoc, const PentominoesPiece& pent) const
{
    return p_data.isBindingPossibleAt(pent.getMatrixModel(), mapLoc) ;
}

/*
 * PentominoesModel : isUnmappingPossible (public const member function)
 * Args             : 
 *                    loc  : Location from where the pentominoes piece needs to be un-placed
 *                           from the crrent matrix model
 *                    pent : which needs to be unplaced from loc defined above.
 * Returns          : bool
 *                    true  - if the current piece can be unplaced from the specified loc.
 *                    false - if the current piece cant be unplaced at the specified loc.
 * Throws           : InvalidOrientationException (through MatrixModel::isBindingPossibleAt)
 * Defn             :
 *                    The check whether the current PentominoesPiece is possible to be
 *                    unplaced at the loc in the current matrix without breaking overlap
 *                    exception. While doing unmapping the check that where ever there is
 *                    one pentominoesPiece model should also have a 1 in MatrixModel is done.
 *
 * TODO             : Handle the exception locally here as this is the final application using
 *                  : MatrixModel class whose member function is throwing this exception
 */
bool
PentominoesModel::isUnmappingPossible(const UIntPair& loc, const PentominoesPiece& pent) const
{
    return p_data.isBindingPossibleAt(pent.getMatrixModel(), loc, true) ;
}

/*
 * PentominoesModel : mapPieceToModel (public non-const member function)
 * Args             : 
 *                    mapAt  : Location where the pentominoes piece needs to be placed in the
 *                             current matrix model
 *                    pent   : PentominoesPiece which needs to be placed at mapLoc defined above.
 * Returns          : bool
 *                    true  - if the current is mapped on the current model at the specified loc.
 *                    false - if the current piece cant be mapped at the specified loc.
 * Throws           : InvalidOrientationException (through MatrixModel::bindMatrixAt)
 * Defn             :
 *                    Map the current PentominoesPiece at the loc in the current matrix model
 *                    without breaking overlap exception. 
 * TODO             : Handle the exception locally here as this is the final application using
 *                  : MatrixModel class whose member function is throwing this exception
 */
bool
PentominoesModel::mapPieceToModel(const UIntPair& mapAt, PentominoesPiece& pent)
{
    try
    {
        p_data.bindMatrixAt(pent.getMatrixModel(), mapAt) ;
    }
    catch(BindException& ex) {
        std::cout << "Exception : "<<ex.what()<<std::endl ;
	return false ;
    }
    m_pieces[&pent] = mapAt ;
    return true ;
}

/*
 * PentominoesModel : unmapPieceFromModel (public non-const member function)
 * Args             : 
 *                    mapAt  : Location from where the pentominoes piece needs to be unplaced
 *                             from the crrent matrix model
 *                    pent   : PentominoesPiece which needs to be unplaced from mapAt defined
 *                             above.
 * Returns          : bool
 *                    true  - if the current is unmapped from the current model from the
 *                            specified loc.
 *                    false - if the current piece cant be unmapped from the specified loc.
 * Throws           : InvalidOrientationException (through MatrixModel::unbindMatrixFrom)
 * Defn             :
 *                    Unmaps the current PentominoesPiece from the loc in the current matrix
 *                    model without breaking overlap exception. 
 * TODO             : Handle the exception locally here as this is the final application using
 *                  : MatrixModel class whose member function is throwing this exception
 */
bool
PentominoesModel::unmapPieceFromModel(const UIntPair& mapAt, PentominoesPiece& pent)
{
    if (m_pieces.find(&pent) == m_pieces.end())
        return false ;
    try
    {
        p_data.unbindMatrixFrom(pent.getMatrixModel(), mapAt) ;
    }
    catch(UnbindException& ex)
    {
        std::cout <<"Exception : "<<ex.what()<<" While unbinding piece from Model...\n" ;
        return false ;
    }
    catch(...)  
    {
        std::cout <<"Generic Exception Occured,  while unbinding piece from Model...\n" ;
	return false ;
    }
    m_pieces.erase(&pent) ;
    return true ;
}

/*
 * PentominoesModel : isGoalModel (public const member function)
 * Args             : Nothing
 * Returns          : bool
 *                    true  - if the current matrix model is indeed qualifies fro a goal model
 *                    false - if the current matrix dows not qualify for a goal model
 * Throws           : Nothing
 * Defn             :
 *                    Return the value of m_goalModel which signifies whether the current
 *                    model is a goal model or not.
 */
bool
PentominoesModel::isGoalModel() const
{
    return m_goalModel ;
}

/*
 * PentominoesModel : extractPentominoesState (public const member function)
 * Args             : SolnSet : To be populated by the function
 * Returns          : Nothing
 * Throws           : Nothing
 * Defn             :
 *                    The solution being constructed is present in the hash_map
 *                    as a collection of (hash_map) (PentominoesPiece, Loc where the piece is
 *                    placed) which is copied to more meaningful representation of vector of
 *                    SolSetItem which is basically a tuple of (char, Orientation, Loc),
 *                    the char represents the PentominoesPiece.
 */
void
PentominoesModel::extractPentominoesState(std::vector<SolnSetItem>& solnSet) const
{
    hash_map<PentominoesPiece*, 
                  UIntPair, 
                  hash<PentominoesPiece*> >::const_iterator itr = m_pieces.begin(); 
    hash_map<PentominoesPiece*, 
                  UIntPair, 
                  hash<PentominoesPiece*> >::const_iterator itrE = m_pieces.end() ;
    for(; itr != itrE; ++itr) {
        solnSet.push_back(boost::make_tuple(itr->first->getAlphabet(),
	  				    itr->first->getOrientation(),
					    itr->second)) ;
    }
    return ;
}

/*
 * PentominoesModel : getNewModelWithSelfTraits (public const member function)
 * Args             : SolnSet : To be populated by the function
 * Returns          : Nothing
 * Throws           : Nothing
 * Defn             :
 *                    This function creates a new PentominoesModel which has the same 
 *                    dimension as the current model. The pieces form the current model 
 *                    is not copied to the current PentominoesModel and nor does the
 *                    m_goalModel, which make it a non-goal-model.
 */
Model*
PentominoesModel::getNewModelWithSelfTraits() const 
{
    UIntPair curDimension = getDimension() ;
    PentominoesModel* p_model = new PentominoesModel(curDimension) ;
    return p_model ;
}

//Implementation of Function for Pentominoes pices derived out of Item class

/*
 * PentominoesPiece : Constructor   (public)
 * Args             : alphabet : Alphabet which represents the pentominoes piece.
 * Returns          : Constructed PentominoesPiece object...
 * Throws           : InvalidLetterException(through initializeMatrixModel)
 * Defn             :
 *                    Builds a PentominoesPiece representing the alphabet, basically
 *                    as part of intialization, the matrixModel of the piece is
 *                    initialized and its orientation is set as R0.
 */
PentominoesPiece::PentominoesPiece(Pentominoe_Alphabet alphabet) : m_letter(alphabet),
                                                                   m_bitmapModel()
{
    initializeMatrixModel() ;
}

/*
 * PentominoesPiece : Destructor   (public)
 * Args             : Nothing
 * Returns          : Nothing
 * Throws           : Nothing
 * Defn             :
 *                    Destroys the PentominoesPiece by clearing the MatrixModel representing
 *                    the piece.
 */
PentominoesPiece::~PentominoesPiece()
{
    m_bitmapModel.clearModel() ;
}

/*
 * PentominoesPiece : perturb   (public non-const member function)
 * Args             : Nothing
 * Returns          : bool
 *                    true  - If perturbation is successful
 *                    false - If perturbation is unsuccessful
 * Throws           : Nothing
 * Defn             :
 *                    Changes the orientation of the piece from R0 to FR270. At every call
 *                    to this function the piece changes its orientation to the next possible
 *                    orientation and returns true. When the orientation comes back to be set
 *                    to R0(from where the perturbation) would have started, the orientaion is
 *                    just set to R0, and false is returned.
 */
bool
PentominoesPiece::perturb()
{
    Orientation curOrientation = getOrientation() ;
    Orientation nxtOrientation = (Orientation)((curOrientation + 1) % MAXORIENT) ;
    this->setOrientation(nxtOrientation) ;
//     if (nxtOrientation == R0) 
//         return false ;
//     return true ;
#ifdef __DEBUG1__
    //std::cout << "Setting orientation of the piece as "<<OrientationStr[nxtOrientation]<<std::endl ;
#endif    
    switch(m_letter) {
        case ALPHA_L :
        case ALPHA_Y :
        case ALPHA_P :
        case ALPHA_F :
        case ALPHA_N :
        case ALPHA_Z :
        case ALPHA_W :
            if (nxtOrientation == R0) 
                return false ;
	    return true ;
        case ALPHA_V :
        case ALPHA_T :
        case ALPHA_U :
            if (nxtOrientation == FR0) 
                return false ;
	    return true ;
        case ALPHA_I :
            if (nxtOrientation == R180) 
                return false ;
	    return true ;
        case ALPHA_X:
            if (nxtOrientation == R90) 
                return false ;
	    return true ;
        default :
  	    return false ;
    }
    return true ;
}

/*
 * PentominoesPiece : getAlphabet   (public const member function)
 * Args             : Nothing
 * Returns          : char : The alphabet which represent the pentominoes piece
 * Throws           : InvalidLetterException.
 * Defn             :
 *                    Depending upon the alphabet represented by PentominoesPiece, the
 *                    equivalent char is returned.
 */
char
PentominoesPiece::getAlphabet() const
{
    if (m_letter > ALPHA_X || m_letter < ALPHA_L)
        throw InvalidLetterException(m_letter) ;
    return PentominoeChars[m_letter] ;
}

/*
 * PentominoesPiece : getOrientationStr   (public const member function)
 * Args             : Nothing
 * Returns          : std::string : The string which describe the current orientation of the
 *                    PentominoesPiece
 * Throws           : InvalidOrientationException.
 * Defn             :
 *                    Depending upon the orientation of the PentominoesPiece, the equivalent
 *                    string is returned.
 */
std::string
PentominoesPiece::getOrientationStr() const
{
    Orientation orient = getOrientation() ;
    if (orient < R0 || orient >= MAXORIENT)
        throw InvalidOrientationException(orient) ;
    return OrientationStr[orient] ;    
}

/*
 * PentominoesPiece : getPieceInfo   (public const member function)
 * Args             : Nothing
 * Returns          : std::string : The string which describe the current complete info of
 *                    the PentominoesPiece
 * Throws           : Nothing
 * Defn             :
 *                    The full info(Alphabet, Orientation) of the piece is returned in form
 *                    of std::string
 */
std::string
PentominoesPiece::getPieceInfo() const
{
    std::string info("Piece : ") ;
    info.push_back(this->getAlphabet()) ;
    info += " Orientation : " ;
    info += this->getOrientationStr() ;
    return info ;
}

/*
 * PentominoesPiece : initializeMatrixModel   (private non-const member function)
 * Args             : Nothing
 * Returns          : Nothing
 * Throws           : InvalidLetterException
 * Defn             :
 *                    Depending upon the letter which the pentominoes piece is representing,
 *                    its matrixModel is initialized, note that different piece will have
 *                    different bounding box.
 */
void
PentominoesPiece::initializeMatrixModel()
{
    // TBD : set the values of row and col properly...
    switch(m_letter)
    {
        case ALPHA_L :
            m_bitmapModel.initialize(4, 2) ; 
            m_bitmapModel.setValAt(0, 0, true, false) ;
            m_bitmapModel.setValAt(1, 0, true, false) ;
            m_bitmapModel.setValAt(2, 0, true, false) ;
            m_bitmapModel.setValAt(3, 0, true, false) ;
            m_bitmapModel.setValAt(3, 1, true, false) ;
	    return ;
        case ALPHA_V :
            m_bitmapModel.initialize(3, 3) ; 
            m_bitmapModel.setValAt(0, 0, true, false) ;
            m_bitmapModel.setValAt(1, 0, true, false) ;
            m_bitmapModel.setValAt(2, 0, true, false) ;
            m_bitmapModel.setValAt(2, 1, true, false) ;
            m_bitmapModel.setValAt(2, 2, true, false) ;
	    return ;
	case ALPHA_Y :
            m_bitmapModel.initialize(4, 2) ; 
            m_bitmapModel.setValAt(0, 1, true, false) ;
            m_bitmapModel.setValAt(1, 0, true, false) ;
            m_bitmapModel.setValAt(1, 1, true, false) ;
            m_bitmapModel.setValAt(2, 1, true, false) ;
            m_bitmapModel.setValAt(3, 1, true, false) ;
	    return ;
        case ALPHA_T :
            m_bitmapModel.initialize(3, 3) ; 
            m_bitmapModel.setValAt(0, 0, true, false) ;
            m_bitmapModel.setValAt(0, 1, true, false) ;
            m_bitmapModel.setValAt(0, 2, true, false) ;
            m_bitmapModel.setValAt(1, 1, true, false) ;
            m_bitmapModel.setValAt(2, 1, true, false) ;
	    return ;
        case ALPHA_P :
            m_bitmapModel.initialize(3, 2) ; 
            m_bitmapModel.setValAt(0, 0, true, false) ;
            m_bitmapModel.setValAt(0, 1, true, false) ;
            m_bitmapModel.setValAt(1, 0, true, false) ;
            m_bitmapModel.setValAt(1, 1, true, false) ;
            m_bitmapModel.setValAt(2, 0, true, false) ;
	    return ;
        case ALPHA_U :
            m_bitmapModel.initialize(2, 3) ; 
            m_bitmapModel.setValAt(0, 0, true, false) ;
            m_bitmapModel.setValAt(0, 2, true, false) ;
            m_bitmapModel.setValAt(1, 0, true, false) ;
            m_bitmapModel.setValAt(1, 1, true, false) ;
            m_bitmapModel.setValAt(1, 2, true, false) ;
	    return ;
        case ALPHA_F :
            m_bitmapModel.initialize(3, 3) ; 
            m_bitmapModel.setValAt(0, 1, true, false) ;
            m_bitmapModel.setValAt(0, 2, true, false) ;
            m_bitmapModel.setValAt(1, 0, true, false) ;
            m_bitmapModel.setValAt(1, 1, true, false) ;
            m_bitmapModel.setValAt(2, 1, true, false) ;
	    return ;
        case ALPHA_N :
            m_bitmapModel.initialize(4, 2) ; 
            m_bitmapModel.setValAt(0, 0, true, false) ;
            m_bitmapModel.setValAt(1, 0, true, false) ;
            m_bitmapModel.setValAt(1, 1, true, false) ;
            m_bitmapModel.setValAt(2, 1, true, false) ;
            m_bitmapModel.setValAt(3, 1, true, false) ;
	    return ;
        case ALPHA_Z :
            m_bitmapModel.initialize(3, 3) ;             
            m_bitmapModel.setValAt(0, 0, true, false) ;
            m_bitmapModel.setValAt(0, 1, true, false) ;
            m_bitmapModel.setValAt(1, 1, true, false) ;
            m_bitmapModel.setValAt(2, 1, true, false) ;
            m_bitmapModel.setValAt(2, 2, true, false) ;
	    return ;
        case ALPHA_I :
            m_bitmapModel.initialize(5, 1) ;             
            m_bitmapModel.setValAt(0, 0, true, false) ;
            m_bitmapModel.setValAt(1, 0, true, false) ;
            m_bitmapModel.setValAt(2, 0, true, false) ;
            m_bitmapModel.setValAt(3, 0, true, false) ;
            m_bitmapModel.setValAt(4, 0, true, false) ;
	    return ;
        case ALPHA_W :
            m_bitmapModel.initialize(3, 3) ;             
            m_bitmapModel.setValAt(0, 0, true, false) ;
            m_bitmapModel.setValAt(1, 0, true, false) ;
            m_bitmapModel.setValAt(1, 1, true, false) ;
            m_bitmapModel.setValAt(2, 1, true, false) ;
            m_bitmapModel.setValAt(2, 2, true, false) ;
	    return ;
        case ALPHA_X :
            m_bitmapModel.initialize(3, 3) ;             
            m_bitmapModel.setValAt(0, 1, true, false) ;
            m_bitmapModel.setValAt(1, 0, true, false) ;
            m_bitmapModel.setValAt(1, 1, true, false) ;
            m_bitmapModel.setValAt(1, 2, true, false) ;
            m_bitmapModel.setValAt(2, 1, true, false) ;
	    return ;
        default :
	    break ;
    }
    throw InvalidLetterException(m_letter) ;
}

// Implementation of PentominoesState Functionalities
/*
 * PentominoesState : Constructor   (public)
 * Args             : loc  : Location where the pentominoes piece needs to be placed.
 *                    item : PentominoesPiece which will be placed at the loc in the model.
 *                    dir  : dir in which the item should be shifted in an attempt to fit the
 *                           piece in the model.
 *                    (m_shiftVal is initialized to 0 as actual val of shift is found when the
 *                     piece is really attempted to be placed on the model.)
 * Returns          : Constructed PentominoesState object...
 * Throws           : Nothing.
 * Defn             :
 *                    Builds a PentominoesState which tries to place the contained item at the
 *                    location being present in the state. The direction is stored to try to
 *                    be able to push the piece in the stored direction without failing overlap
 *                    constraint.
 */
PentominoesState::PentominoesState(const UIntPair& loc,
                                   PentominoesPiece* p_item,
                                   DIR dir) : State(p_item), m_pieceLoc(loc), m_dir(dir),
                                              m_shiftVal(0), m_originalLoc(loc) 
{
}

/*
 * PentominoesState : Destructor   (public)
 * Args             : Nothing
 * Returns          : Nothing
 * Throws           : Nothing.
 * Defn             :
 *                    Destroys the PentominoesState object.
 */
PentominoesState::~PentominoesState()
{
}

/*
 * PentominoesState : initiateStateForSolution   (public non-const member function)
 * Args             : Nothing
 * Returns          : Nothing
 * Throws           : Nothing
 * Defn             :
 *                    Whenever the state is created, it contains an item and it location.
 *                    The actual owner of the item is PentominoesTree, the item whenever
 *                    tried first time from a state should be in state R0 and the perturbation
 *                    of the state will change the orientation of the item till all orientation
 *                    is tried or a valid overall solutiion is found.
 * Note             : Once the state could not become prt of the solution, the item contained
 *                    in the current state might be tried in other freshly created state,
 *                    hence the item needs to be brought to R0 orientation.
 */
void
PentominoesState::initiateStateForSolution()
{
    try 
    {
        PentominoesPiece* p_pentPiece = dynamic_cast<PentominoesPiece*>(getContainedItem()) ;
        p_pentPiece->setOrientation(R0) ;
    }
    catch(...) // handles the bad_cast
    {
        std::cout << "Can't cast Pentominoes Piece from the item in initiateStateForSolution \n";
        return ;
    }
    return ;    
}

/*
 * PentominoesState : fixStateForSolution   (public non-const member function)
 * Args             : Nothing
 * Returns          : Nothing
 * Throws           : Nothing
 * Defn             :
 *                    Whenever the state is created, its location is also specified, which
 *                    is basically (0,0) loc of matrix-model of PentominoesPiece contained
 *                    by the state. As different piece has different models and its not
 *                    necessary that the piece's model will have a 1 at (0,0), but when a
 *                    piece needs to be placed at the specified loc a 1 is expected, hence
 *                    depending upon the direction of the state, the piece is attempted to
 *                    move either in top or left direction such that the loc has a 1 without
 *                    breaking overlap constraint. This function attempts to shift the piece
 *                    such that a 1 is found at (0,0) and the new loc is set as
 *                    currentLoc - shiftVal.
 */
bool
PentominoesState::fixStateForSolution()
{
    return (this->shiftStateToGetTrueAtLL()) ;
}

/*
 * PentominoesState : applyStateOnModel   (public const member function)
 * Args             : PentominoesModel on which the state needs to be applied.
 * Returns          : bool 
 *                    true  - If the state is successfully applied on the model.
 *                    false - If the state could not be applied on the model, for
 *                            some constraint failed
 * Throws           : Nothing
 *                    Any exception thrown by the function called by this function is
 *                    caught in this function.
 * Defn             :
 *                    Apply the matrix-model of the current item, contained by the state,
 *                    on the model passed as argument, without breaking overlap constraint.
 */
bool
PentominoesState::applyStateOnModel(Model* p_model) const
{
    bool retVal = false ;
    try 
    {
        PentominoesModel* p_pentModel = dynamic_cast<PentominoesModel*>(p_model) ;
        PentominoesPiece* p_pentPiece = dynamic_cast<PentominoesPiece*>(m_pItem) ;
        
        retVal = p_pentModel->mapPieceToModel(m_pieceLoc, *p_pentPiece) ;
    }
    catch(...) // Not handling exceptions as by design its already handled in the func.
               // mapPieceToModel
    {
        return false ;
    }
    return retVal ;
} 

/*
 * PentominoesState : backtrackState   (public const member function)
 * Args             : PentominoesModel on which the state needs to be applied.
 * Returns          : bool 
 *                    true  - If the state is successfully backtracked from the model.
 *                    false - If the state could not be backtracked from the model, for
 *                            some constraint failed
 * Throws           : Nothing
 *                    Any exception thrown by the function called by this function is caught
 *                    in this function.
 * Defn             :
 *                    Unmap the matrix-model of the current item, contained by the state,
 *                    from the model passed as argument, without breaking the constraint
 *                    that model doesn't contain 1 at the pos where the piece contains 1
 *                    after being placed at state's loc with specified orientatation. After
 *                    unmapping the state also resets any shift done to its location by
 *                    fixStateForSolution fn., it also resets the shiftVal.
 */
bool
PentominoesState::backtrackState(Model* p_model) const
{
    bool retVal = false ;
    try 
    {
        PentominoesModel* p_pentModel = dynamic_cast<PentominoesModel*>(p_model) ;
        PentominoesPiece* p_pentPiece = dynamic_cast<PentominoesPiece*>(m_pItem) ;
        retVal = p_pentModel->unmapPieceFromModel(m_pieceLoc, *p_pentPiece) ;
        PentominoesState* p_pentState = const_cast<PentominoesState*>(this) ;
#ifdef __DEBUG1__
//         std::cout << "Backtracking Piece : "<<p_pentPiece->getAlphabet()
//                   << " shiftVal : "<<m_shiftVal
//                   << " Piece Loc : "<<p_pentState->m_pieceLoc.get<0>()
//                   << " ," << p_pentState->m_pieceLoc.get<1>() <<std::endl ;
#endif
        if (m_dir == X_DIR) {
            p_pentState->m_pieceLoc.get<1>() += m_shiftVal ;
        }
        else if (m_dir == Y_DIR) {
            p_pentState->m_pieceLoc.get<0>() += m_shiftVal ;
        }
        p_pentState->m_shiftVal = 0 ;
        p_pentState->m_pieceLoc = m_originalLoc ;
    }
    catch(...)
    {
        return false ;
    }
    return retVal ;
}

/*
 * PentominoesState : printState   (public const member function)
 * Args             : Nothing
 * Returns          : Nothing
 * Throws           : Nothing
 * Defn             :
 *                    Prints the complete info about the current state on stdout.
 */
void
PentominoesState::printState() const
{
    PentominoesPiece* p_pentPiece = dynamic_cast<PentominoesPiece*>(m_pItem) ;
    if (!p_pentPiece) {
        std::cout << "Bad state with Invalid Pentominoes Piece found...\n" ;
	return ;
    }
    std::cout << p_pentPiece->getPieceInfo() << " At " ;
    std::cout << boost::tuples::set_open('[') << boost::tuples::set_close(']') <<
                 boost::tuples::set_delimiter(',') << m_pieceLoc << std::endl ;
    return ;
}

/*
 * PentominoesState : shiftStateToGetTrueAtLL   (public const member function)
 * Args             : Nothing
 * Returns          : Nothing
 * Throws           : Nothing
 * Defn             :
 *                    Calculates the shift that is needed to get a 1 at (0,0) loc throuch 
 *                    MatrixModel::shiftNeededToGetValAtTopLeft. The loc of the state is
 *                    changed accordingly(depending upon the direction of the state) and
 *                    shiftVal is stored in the state.
 */
bool
PentominoesState::shiftStateToGetTrueAtLL()
{
    int val = 0 ;
    try 
    {
        PentominoesPiece* p_pentPiece = dynamic_cast<PentominoesPiece*>(m_pItem) ;
        if (p_pentPiece->getAlphabet() == 'N')
            val = 1 ;
        unsigned int val ;
        if (p_pentPiece->getMatrixModel().shiftNeededToGetValAtTopLeft(true, m_dir, val) == false)
        {
            // Major goof up, throw an exception here...
            // assert(0 && "Bounding Box of PentominoesPiece not proper...") ;
  	    m_shiftVal = 0 ;
            return false ;
        }
        m_shiftVal = val ;
        if (m_dir == X_DIR) {
            if (m_pieceLoc.get<1>() < val)
                return false ;
            m_pieceLoc.get<1>() -= val ;
        }
        else if (m_dir == Y_DIR) {
            if (m_pieceLoc.get<0>() < val)
                return false ;
            
            m_pieceLoc.get<0>() -= val ;
        }
    }
    catch(...)
    {
        return false ;
    }
    return true ;
}

// Constraints implementation.
/*
 * MapConstraint    : isSatisfied   (public const member function)
 * Args             : 
 *                    Model p_model      : Current Model, in which the item contained by
 *                                         state needs to be placed
 *                    Model p_goalModel  : Final goal model, where the current model is trying
 *                                         to go to.
 *                    State p_state      : The state needs to satisfy the contraint, by place
 *                                         the conatined item on model
 * Returns          : bool
 *                    true  - if the constraint will be satisfied 
 *                    false - id the constraint is not satisfied
 * Throws           : InvalidOrientationException (through PentominoesModel::isMappingPossible)
 * Defn             :
 *                     If the matrix-model of the item contained in the state can be mapped
 *                     on the matrix-model of the input model(p_model) without violationg
 *                     mapping constraint i..e if a 1 is already present where the item's
 *                     matrix model is trying to place a 1, the error condn is caused. The
 *                     place where the matrix model of the item need to be placed is contained
 *                     in State.
 *
 * Note             : MapConstraint is basically a PRE_CONSTRAINT i..e , it should be
 *                    satisfied befor the state is applied on the model.
 */
bool
MapConstraint::isSatisfied(const Model* p_model, const Model* p_goalModel,
			   const State* p_toState) const
{
    const PentominoesModel* p_pentModel = dynamic_cast<const PentominoesModel*>(p_model) ;
    const PentominoesState* p_pentState = dynamic_cast<const PentominoesState*>(p_toState) ;
    const PentominoesPiece* p_pentPiece = dynamic_cast<const PentominoesPiece*>(p_toState->getContainedItem()) ;
    (void)p_goalModel ;

    return p_pentModel->isMappingPossible(p_pentState->getPieceLoc(), *p_pentPiece) ;
}

/*
 * GoalConstraint   : isSatisfied   (public const member function)
 * Args             : 
 *                    Model p_model      : Current Model, in which the item contained by
 *                                         state needs to be placed
 *                    Model p_goalModel  : Final goal model, where the current model is trying
 *                                         to go to
 *                    State p_state      : The state needs to satisfy the contraint, by place
 *                                         the conatined item on model
 * Returns          : bool
 *                    true  - if the constraint will be satisfied 
 *                    false - id the constraint is not satisfied
 * Throws           : InvalidOrientationException (through PentominoesModel::isMappingPossible)
 * Defn             :
 *                    This constraint makes sure the the current model being built should
 *                    not have a 1 where the goal model contains a 0(1-0 condition).
 *                    The (0-1 condition) is not needed and later states might populate
 *                    the o posn of the current model with 1, if the goal model contains a 1
 *                    at the pos.
 */
bool
GoalConstraint::isSatisfied(const Model* p_model, const Model* p_goalModel,
			    const State* p_toState) const
{
    const PentominoesModel* p_pentModel = dynamic_cast<const PentominoesModel*>(p_model) ;
    //const PentominoesState* p_pentState = dynamic_cast<const PentominoesState*>(p_toState) ;
    //const PentominoesPiece* p_pentPiece = dynamic_cast<const PentominoesPiece*>(p_toState->getContainedItem()) ;
    const PentominoesModel* p_pentGoalModel = dynamic_cast<const PentominoesModel*>(p_goalModel) ;
    (void)p_toState ;

    UIntPair diffLoc ;
    if (p_pentGoalModel->getMatrixModel().findDiffLoc(diffLoc, false, true,
                                                      p_pentModel->getMatrixModel(),
                                                      X_DIR))
        return false ;
    return true ;
}

/*
 * PentominoesTree  : Constructor   (public)
 * Args             : Nothing
 * Returns          : Constructed PentominoesTree object...
 * Throws           : Nothing.
 * Defn             :
 *                    Builds a PentominoesTree, and intializes the items which needs to be
 *                    used to form the goalModel. It also creates a staeZero wit no
 *                    pentominoesPiece and no Loc. The zero state basically is the first
 *                    driver state from where the solution tree starts getting built.
 */
PentominoesTree::PentominoesTree() : DecisionTree()
{
    initializeItems() ;
    (void)buildStateZero() ;
    buildConstraints() ;
}

/*
 * PentominoesTree  : generateAllChildStates   (public const member function)
 * Args             : 
 *                    Solution curState  : All the states being considered for solution.
 *                    State    p_state   : The state whose child state needs to be generated.
 * Returns          : count of the child states generated for the input state.
 * Throws           : Nothing
 * Defn             :
 *                    Collect all the PentominoesPiece present in the curState, which is
 *                    basically vector of states being collected as part of solution(as they
 *                    have passed the constraints). Do a set_difference with actual collection
 *                    of items the tree stores as set of pieces to work with. The differenece
 *                    is basically a collection of items which should be a part for next set
 *                    of states that should be created. For each item create a state as a child
 *                    state of the input state. The location of each state being created is
 *                    calculated as the first 1 pos in goalModel which is 0 in the current
 *                    model(PentominoesTree owns both the current model being built and the
 *                    goal model). The first 1 pos can be looked for in the matrix-model
 *                    of the goal model in row-major or col-major form(X_DIR or Y_DIR). For
 *                    each such posn a new state is created if they are unique.
 * 
 * TODO             : Do we really need to create two states for two locs???
 */
size_t
PentominoesTree::generateAllChildStates(const Solution& curState, State* p_state) const
{
    UIntPair stateLocX ;
    UIntPair stateLocY ;    
    PentominoesModel* p_pentModel = dynamic_cast<PentominoesModel*>(m_pModel) ;
    PentominoesModel* p_pentGoalModel = dynamic_cast<PentominoesModel*>(m_pGoalModel) ;



    bool locFound = p_pentModel->getMatrixModel().findDiffLoc(stateLocX, false, true, 
                                                              p_pentGoalModel->getMatrixModel(),
                                                              X_DIR) ;
    if (locFound)
        (void)p_pentModel->getMatrixModel().findDiffLoc(stateLocY, false, true, 
                                                        p_pentGoalModel->getMatrixModel(),
                                                        Y_DIR) ;
    else
        return 0 ;

    bool diffLocDifferent = false ;
    if (stateLocX.get<0>() != stateLocY.get<0>() ||
        stateLocX.get<1>() != stateLocY.get<1>())
        diffLocDifferent = true ;

    //p_pentModel->getMatrixModel().getLowestPosWithVal(false, stateLoc) ;
    std::set<Item*, ltItem> itemsInSolnSet ;
    std::set<Item*, ltItem> itemsForChildStates ;

#ifdef __DEBUG1__
    bool debugCond = false ;
    if (curState.size() == 7)
        debugCond = true ;

    char pieces[7] = { 'T', 'F', 'U', 'X', 'Y', 'Z', 'P' } ;
    Orientation orients[7] = { R90, FR180, R180, R0, FR90, R90, R180} ;
    int idx = 0 ;
#endif

    Solution::const_iterator itr  = curState.begin() ;
    Solution::const_iterator itrE = curState.end() ;
    for(; itr != itrE; ++itr) {
        const State* p_state = *itr ;
        itemsInSolnSet.insert(p_state->getContainedItem()) ;
#ifdef __DEBUG1__
        if (debugCond) {
            PentominoesPiece* p_piece = dynamic_cast<PentominoesPiece*>(p_state->getContainedItem()) ;
            if (p_piece->getAlphabet() != pieces[idx] || 
		p_piece->getOrientation() != orients[idx])
	        debugCond = false ;
            idx++ ;
	}
#endif
    }    

    std::set_difference(m_items.begin(), m_items.end(),
			itemsInSolnSet.begin(), itemsInSolnSet.end(),
			std::inserter(itemsForChildStates, itemsForChildStates.begin())) ;

    if (itemsForChildStates.empty())
        return 0 ;

#ifdef __DEBUG1__
    if (debugCond) {
        printSolution(curState) ;
        std::cout << "\n Corresponding Model = \n" ;
        p_pentModel->printModel() ;
        std::cout << "Childs Generated for P = \n" ;
    }
#endif    

    std::set<Item*, ltItem>::iterator itr1 = itemsForChildStates.begin() ;
    std::set<Item*, ltItem>::iterator itr1E = itemsForChildStates.end() ;
    for(; itr1 != itr1E; ++itr1) {
        PentominoesPiece* p_pentPiece = dynamic_cast<PentominoesPiece*>(*itr1) ;
        p_pentPiece->setOrientation(R0) ;
        PentominoesState* p_childStateX = new PentominoesState(stateLocX, p_pentPiece, X_DIR) ;
        p_state->addChildState(p_childStateX) ;
#ifdef __DEBUG1__
        if (debugCond)
	  p_childStateX->printState() ;
#endif
//         if (diffLocDifferent) {
//             PentominoesState* p_childStateY = new PentominoesState(stateLocY,
//                                                                    p_pentPiece, Y_DIR) ;
//             p_state->addChildState(p_childStateY) ;
//         }
    }
#ifdef __DEBUG1__
    if (debugCond)
      std::cout << "All Children printed...\n" ;
#endif
    return itemsForChildStates.size() ;
}

/*
 * PentominoesTree  : generateNextChildState   (public const member function)
 * Args             : 
 *                    State   sibling    : The last state which this function generated.
 *                    Solution curState  : All the states being considered for solution.
 *                    State    p_state   : The state whose child state needs to be generated.
 * Returns          : count of the child states generated for the input state.
 * Throws           : Nothing
 * Defn             :
 *                    Collect all the PentominoesPiece present in the curState, which is
 *                    basically vector of states being collected as part of solution(as they
 *                    have passed the constraints). Do a set_difference with actual collection
 *                    of items the tree stores as set of pieces to work with. The differenece
 *                    is basically a collection of items which should be a part for next set
 *                    of states that should be created. For each item check whether it is
 *                    contained in the prevSiblingState if sibling state is non NULL. Once a
 *                    State is found with the item in sibling state, go to the next item in
 *                    the difference set and create two more state for X and Y empty posns
 *                    and add the two state as a child state of the input state. The location
 *                    of each state being created is calculated as the first 1 pos in goalModel
 *                    which is 0 in the current model(PentominoesTree owns both the current
 *                    model being built and the goal model). The first 1 pos can be looked for
 *                    in the matrix-model of the goal model in row-major or col-major
 *                    form(X_DIR or Y_DIR). For each such posn a new state is created if they
 *                    are unique. Once the two ne states are generated by the function, it
 *                    returns a count(if both the states are generated then it returns 2
 *                    else 1). 
 * 
 * TODO             : Do we really need to create two states for two locs???
 */
size_t
PentominoesTree::generateNextChildState(const State* p_prevSiblingState,
				        const Solution& states,
				        State* p_parentState) const
{
    UIntPair stateLocX ;
    UIntPair stateLocY ;    
    PentominoesModel* p_pentModel = dynamic_cast<PentominoesModel*>(m_pModel) ;
    PentominoesModel* p_pentGoalModel = dynamic_cast<PentominoesModel*>(m_pGoalModel) ;

    bool locFound = p_pentModel->getMatrixModel().findDiffLoc(stateLocX, false, true, 
                                                              p_pentGoalModel->getMatrixModel(),
                                                              X_DIR) ;
    if (locFound)
        (void)p_pentModel->getMatrixModel().findDiffLoc(stateLocX, false, true, 
                                                        p_pentGoalModel->getMatrixModel(),
                                                        X_DIR) ;
    else
        return 0 ;

    bool diffLocDifferent = false ;
    if (stateLocX.get<0>() != stateLocY.get<0>() ||
        stateLocX.get<1>() != stateLocY.get<1>())
        diffLocDifferent = true ;
    
    std::set<Item*, ltItem> itemsInSolnSet ;
    std::set<Item*, ltItem> itemsForChildStates ;

    Solution::const_iterator itr  = states.begin() ;
    Solution::const_iterator itrE = states.end() ;
    for(; itr != itrE; ++itr) {
        const State* p_state = *itr ;
        itemsInSolnSet.insert(p_state->getContainedItem()) ;
    }


    Item* p_prevItem = NULL ; 
    if(p_prevSiblingState) 
        p_prevItem = p_prevSiblingState->getContainedItem() ;

    std::set_difference(m_items.begin(), m_items.end(),
			itemsInSolnSet.begin(), itemsInSolnSet.end(),
			std::inserter(itemsForChildStates, itemsForChildStates.begin())) ;

    if (itemsForChildStates.empty())
        return false ;

    std::set<Item*, ltItem>::iterator itr1 ;
    std::set<Item*, ltItem>::iterator itr1E = itemsForChildStates.end() ;    
    if (p_prevItem) {
        itr1 = itemsForChildStates.find(p_prevItem) ;
        if (itr1 == itr1E)
            return 0 ;
        itr1++ ;
    } else {
        itr1 = itemsForChildStates.begin() ;
        if (itr1 == itr1E)
            return 0 ;        
    }

    PentominoesPiece* p_pentPiece = dynamic_cast<PentominoesPiece*>(*itr1) ;
    p_pentPiece->setOrientation(R0) ;
    PentominoesState* p_childStateX = new PentominoesState(stateLocX, p_pentPiece, X_DIR) ;
    p_parentState->addChildState(p_childStateX) ;
//     if (diffLocDifferent) {
//         PentominoesState* p_childStateY = new PentominoesState(stateLocY,
//                                                                p_pentPiece, Y_DIR) ;
//         p_parentState->addChildState(p_childStateY) ;
//         return 2 ;
//     }
    

    return 1 ;
}

/*
 * PentominoesTree  : initializeModel   (private non-const member function)
 * Args             : Nothing
 * Returns          : bool - always true
 * Throws           : Nothing
 * Defn             :
 *                    This function merely needs to be present as the base class has it
 *                    as virtual function. Till the current implementation of the 
 */
bool
PentominoesTree::initializeModel()
{
    return true ;
}

/*
 * PentominoesTree  : buildStateZero   (private non-const member function)
 * Args             : Nothing
 * Returns          : bool - always true
 * Throws           : Nothing
 * Defn             :
 *                    This function creates state-zero, without any pentominoes piece or
 *                    loc, the main intention of this state is to start looking for a soln
 *                    which matches the goal model.
 */
bool
PentominoesTree::buildStateZero()
{
    PentominoesState* p_pentState = new PentominoesState() ;
    m_pStateZero = p_pentState ;
    return true ;
}

/*
 * PentominoesTree  : buildConstraints   (private non-const member function)
 * Args             : Nothing
 * Returns          : Nothing
 * Throws           : Nothing
 * Defn             :
 *                    This function creates constraints(MapConstraint and GoalConstraint) which
 *                    needs to besatisfied to solve the pentominoesPuzzle.
 */
void
PentominoesTree::buildConstraints()
{
    std::string mapConsName("Map Constraint") ;
    MapConstraint* p_mapCons = new MapConstraint(mapConsName) ;

    std::string goalConsName("Goal Constraint") ;
    GoalConstraint* p_goalCons = new GoalConstraint(goalConsName) ;

    this->addConstraint(p_mapCons) ;
    this->addConstraint(p_goalCons) ;    
}

/*
 * PentominoesTree  : initializeItems   (private non-const member function)
 * Args             : Nothing
 * Returns          : Nothing
 * Throws           : Nothing
 * Defn             :
 *                    This function creates Items which needs to be used to make the goal model.
 */
void
PentominoesTree::initializeItems()
{
//     PentominoesPiece* p_pentL = new PentominoesPiece(ALPHA_L) ;
//     PentominoesPiece* p_pentV = new PentominoesPiece(ALPHA_V) ;
//     PentominoesPiece* p_pentY = new PentominoesPiece(ALPHA_Y) ;
//     PentominoesPiece* p_pentP = new PentominoesPiece(ALPHA_P) ;
//     PentominoesPiece* p_pentU = new PentominoesPiece(ALPHA_U) ;
//     PentominoesPiece* p_pentF = new PentominoesPiece(ALPHA_F) ;
//     PentominoesPiece* p_pentN = new PentominoesPiece(ALPHA_N) ;
//     PentominoesPiece* p_pentZ = new PentominoesPiece(ALPHA_Z) ;
//     PentominoesPiece* p_pentI = new PentominoesPiece(ALPHA_I) ;
//     PentominoesPiece* p_pentW = new PentominoesPiece(ALPHA_W) ;
//     PentominoesPiece* p_pentX = new PentominoesPiece(ALPHA_X) ;
//     PentominoesPiece* p_pentT = new PentominoesPiece(ALPHA_T) ;

    PentominoesPiece* p_pentT = new PentominoesPiece(ALPHA_T) ;
    PentominoesPiece* p_pentF = new PentominoesPiece(ALPHA_F) ;
    PentominoesPiece* p_pentU = new PentominoesPiece(ALPHA_U) ;
    PentominoesPiece* p_pentX = new PentominoesPiece(ALPHA_X) ;
    PentominoesPiece* p_pentY = new PentominoesPiece(ALPHA_Y) ;
    PentominoesPiece* p_pentZ = new PentominoesPiece(ALPHA_Z) ;
    PentominoesPiece* p_pentP = new PentominoesPiece(ALPHA_P) ;
    PentominoesPiece* p_pentN = new PentominoesPiece(ALPHA_N) ;
    PentominoesPiece* p_pentL = new PentominoesPiece(ALPHA_L) ;
    PentominoesPiece* p_pentV = new PentominoesPiece(ALPHA_V) ;
    PentominoesPiece* p_pentI = new PentominoesPiece(ALPHA_I) ;
    PentominoesPiece* p_pentW = new PentominoesPiece(ALPHA_W) ;

    m_items.insert(p_pentL) ;
    m_items.insert(p_pentV) ;
    m_items.insert(p_pentY) ;
    m_items.insert(p_pentP) ;
    m_items.insert(p_pentU) ;
    m_items.insert(p_pentF) ;
    m_items.insert(p_pentN) ;
    m_items.insert(p_pentZ) ;
    m_items.insert(p_pentI) ;
    m_items.insert(p_pentW) ;
    m_items.insert(p_pentX) ;
    m_items.insert(p_pentT) ;

    return  ;
}

void
PentominoesTree::printSolution(const Solution& states) const
{
    if(!m_pModel) {
        std::cout << "No Model Built yet..." ;
	return ;
    }
    const PentominoesModel* p_pentModel = dynamic_cast<PentominoesModel*>(m_pModel) ;
    if (!p_pentModel) {
        std::cout << "Not a valid Pentominoes Model\n" ;
	return ;
    }

    UIntPair matDimension = p_pentModel->getDimension() ;

    unsigned int rows1 = p_pentModel->getDimension().get<0>() ;
    unsigned int cols1 = p_pentModel->getDimension().get<1>() ;

    char** pentMatrix = NULL ;
    pentMatrix = new char*[rows1] ;
    for(unsigned int i = 0; i < rows1; ++i) {
        pentMatrix[i] = new char[cols1] ;
        for(unsigned int j = 0; j < cols1; ++j) 
	    pentMatrix[i][j] = '0' ;
    }

    

    Solution::const_iterator itr = states.begin() ;
    Solution::const_iterator itrE = states.end() ;
    for(; itr != itrE; ++itr) {
        PentominoesState* p_pentState = dynamic_cast<PentominoesState*>(*itr) ;
        p_pentState->printState() ;
        PentominoesPiece* p_pentPiece = dynamic_cast<PentominoesPiece*>(p_pentState->getContainedItem()) ;
        UIntPair pieceLoc = p_pentState->getPieceLoc() ;
        unsigned int i1 = (int)pieceLoc.get<0>() ;
	unsigned int j1 = (int)pieceLoc.get<1>() ;
        unsigned int i2, j2 ;

        unsigned int rows2 = p_pentPiece->getMatrixModel().numRows() ;
        unsigned int cols2 = p_pentPiece->getMatrixModel().numCols() ;
        for(i2 = 0; i1 < rows1 && i2 < rows2; ++i1, ++i2) {
            j1 = (int)pieceLoc.get<1>() ;
            j2 = 0 ;
            for(; j1 < cols1 && j2 < cols2; ++j1, ++j2) {
	        if (p_pentPiece->getMatrixModel().getValAt(i2, j2, true))
  		    pentMatrix[i1][j1] = p_pentPiece->getAlphabet() ;
            }
        } 
    }
    for(unsigned int i = 0 ; i < rows1; ++i)  {
        for(unsigned int j = 0 ; j < cols1; ++j) 
	    std::cout << pentMatrix[i][j] ;
	std::cout << std::endl ;
    }
}

std::string
PentominoesTree::getCurSolutionStateStr(const Solution& states) const
{
    std::string resStr ;
    std::stringstream oss ;

    int idx = 1 ;

    Solution::const_iterator itr = states.begin() ;
    Solution::const_iterator itrE = states.end() ;
    for(; itr != itrE; ++itr, ++idx) {
        PentominoesState* p_pentState = dynamic_cast<PentominoesState*>(*itr) ;
        p_pentState->printState() ;
        PentominoesPiece* p_pentPiece = dynamic_cast<PentominoesPiece*>(p_pentState->getContainedItem()) ;
        UIntPair pieceLoc = p_pentState->getPieceLoc() ;
  	oss << idx << ". " << p_pentPiece->getPieceInfo() << " At " ;
        oss << boost::tuples::set_open('[') << boost::tuples::set_close(']') <<
	       boost::tuples::set_delimiter(',') << pieceLoc << std::endl ;
    }
    resStr = oss.str() ;
    return resStr ;
}
